#include <bits/stdc++.h>
using namespace std;
 
#define co(n) cout<<n<<endl;
const double eps=1e-10,pi=3.1415926535898;
const int mod=1e9+7,maxn=1e5+10;
int T,n,m,k,x,y,a[maxn],b[maxn];
 
int main(int argc, char const *argv[]) {
    //init();
    T = 1;
    scanf("%d", &T);
    for (int _=1;_<=T;++_) {
        long long ans=0;
        memset(a, 0xff, sizeof(a));
        scanf("%d %d %d", &n, &m, &k);
        a[k] = 0;
        for (int i=1;i<=m;++i) {
            scanf("%d %d", &x, &y);
            if (a[x] == -1 and a[y] == -1) continue;
            if (a[x] == -1) {
                a[x] = a[y];
                ++a[y];
            }
            else if (a[y] == -1) {
                a[y] = a[x];
                ++a[x];
            }
            else {
                int p=min(a[x]+1, a[y]),q=min(a[x], a[y]+1);
                a[x] = p;
                a[y] = q;
            }
        }
        for (int i=1;i<n;++i) {
            printf("%d ", a[i]);
        }
        printf("%d\n", a[n]);
    }
    return 0;
}
 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
clock_t clk;
clk = clock();
if(clock() - clk > CLOCKS_PER_SEC * 0.9) 
      T
W     L
A C M E R
  E L   E
    E
*/