#include<bits/stdc++.h>
#define db double
#define reg register
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ull unsigned long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=head[a];i;i=e[i].nxt)


using namespace std;
bool Handsome;
inline int rd(){
    reg int x=0;reg char o=getchar();reg bool O=0;
    for(;o<48 || 57<o;o=getchar())if(o=='-')O=1;
    for(;48<=o && o<=57;o=getchar())x=(x<<1)+(x<<3)+(o^48);
    return O?-x:x;
}
inline void Mi(int &x,int y){if(x>y && (x=y));}
inline void Mx(int &x,int y){if(x<y && (x=y));}
const int M=1e5+5,inf=1e9;
int n,m,k,f[M],t[M];
void Clear(){
    memset(f,0x7f,sizeof(f));
}
void solve(){
    n=rd(),m=rd(),k=rd();f[k]=0;
    rep(i,1,m){
        int x=rd(),y=rd();
        int f1=f[x],f2=f[y];
        f[x]=min(f1+1,f2);
        f[y]=min(f1,f2+1);
    }
    rep(i,1,n){
        if(f[i]>inf)f[i]=-1;
        printf("%d",f[i]);
        if(i<n)putchar(' ');
    }
    puts("");
}
bool Most;
int main(){
//    printf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0);
    int t=rd();
    while(t--)Clear(),solve();
    return 0;
}