#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;

int read(); ll readll();

int n, m, k, f[100009];
int main(){
    int cas = read();
    while (cas--){
        scanf("%d %d %d", &n, &m, &k);
        int i;
        for (i = 1; i <= n; i++) f[i] = m + 1;
        f[k] = 0;
        for (i = 1; i <= m; i++){
            int l = read(), r = read();
            if (l == r) continue;
            int x = f[l], y = f[r];
            f[l] = min(x + 1, y); f[r] = min(x, y + 1);    
        }
        for (i = 1; i <= n; i++) printf("%d%c", f[i] > m ? -1 : f[i], i < n ? ' ' : '\n');
    }
    return 0;    
}

int read(){
    int x=0; char ch=getchar(); bool flag=0;
    while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
    while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return flag?-x:x;
}
ll readll(){
    ll x=0; char ch=getchar(); bool flag=0;
    while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
    while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return flag?-x:x;
}