#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
bool f2;
char IO;
int rd(){
    int num=0;bool f=0;
    while(IO=getchar(),IO<48||IO>57)if(IO=='-')f=1;
    do num=(num<<1)+(num<<3)+(IO^48);
    while(IO=getchar(),IO>=48&&IO<=57);
    return f?-num:num;
}
int dp[100005];
bool f1;
int main(){
//    cout<<1.0*(&f1-&f2)/1024.0/1024.0<<endl;
    int T=rd();
    int n,m,K;
    while(T--){
        memset(dp,63,sizeof(dp));
        n=rd(),m=rd(),K=rd();
        dp[K]=0;
        for(int i=1,u,v,tu,tv;i<=m;++i){
            u=rd(),v=rd();
            tu=dp[u],tv=dp[v];
            dp[v]=min(tv+1,tu);
            dp[u]=min(tu+1,tv);
        }
        for(int i=1;i<=n;++i){
            if(dp[i]!=0x3f3f3f3f)
                printf("%d",dp[i]);
            else printf("-1");
            if(i!=n)printf(" ");
        }
        puts("");
    }
    return 0;
}