#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define in(a) a=read()
#define out(a) printf("%d\n",a)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(a,x) memset(a,x,sizeof(a))
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 1000000007
void MOD(int &x){x-=x>=mod?mod:0;}
#define maxn 500010
#define inf (1<<30)

int l,head[maxn],to[maxn],nxt[maxn],v[maxn];
void add(int x,int y,int z){
    swap(x,y);
    l++;nxt[l]=head[x];head[x]=l;to[l]=y;v[l]=z;
}
int bfs[maxn*2],d[maxn];
int a[maxn],b[maxn],id[maxn];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    int t;
    in(t);
    while(t--){
        int n,m,k;
        in(n);in(m);in(k);
        l=0;clr(head,0);
        FOR(i,1,m){
            in(a[i]),in(b[i]);
        }
        FOR(i,1,n)id[i]=i;
        int num=n;
        FORD(i,m,1){
            num++;num++;
            add(id[a[i]],num-1,1);
            add(id[a[i]],num,0);
            add(id[b[i]],num-1,0);
            add(id[b[i]],num,1);
            id[a[i]]=num-1;id[b[i]]=num;
        }
        int l=3e5,r=3e5;
        FOR(i,1,num)d[i]=inf;
        bfs[r++]=id[k];d[id[k]]=0;
        while(l<r){
            int x=bfs[l++];
            FORL(i,x){
                int c=to[i];
                if(d[c]==inf){
                    d[c]=d[x]+v[i];
                    if(!v[i])bfs[--l]=c;
                    else bfs[r++]=c;
                    bfs[r++]=c;
                }
            }
        }
        FOR(i,1,n){
            if(d[i]==inf)printf("-1");
            else printf("%d",d[i]);
            if(i!=n)putchar(' ');
        }
        puts("");
    }
}