#include<bits/stdc++.h>
using namespace std;

#define Mod(x) (x>=P)&&(x-=P)
#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,b) for(int i=hd[a];i;i=nxt[i])

typedef long long ll;
void Max(int &x,int y){x<y&&(x=y);}
void Min(int &x,int y){x>y&&(x=y);}

bool vio;
char IO;
int rd(int res=0){
    bool f=0;
    while(IO=getchar(),IO<48||IO>57)
        f|=IO=='-';
    do res=(res<<1)+(res<<3)+(IO^48);
    while(IO=getchar(),isdigit(IO));
    return f?-res:res;
}
const int M=1e5+10;
int dis[M];
bool let;
int main(){
    //cerr<<(&vio-&let)/1024.0/1024<<endl;
    rep(cas,1,rd()){
        int n=rd(),m=rd(),k=rd();
        rep(i,1,n)dis[i]=1e9+10;
        dis[k]=0;
        rep(i,1,m){
            int a=rd(),b=rd();
            int t1=dis[a],t2=dis[b];
            dis[a]=min(t2,t1+1);
            dis[b]=min(t1,t2+1);
        }
        printf("%d",dis[1]>1e9?-1:dis[1]);
        rep(i,2,n)printf(" %d",dis[i]>1e9?-1:dis[i]);
        puts("");
    }
}