#include<bits/stdc++.h>
using namespace std;
const int N=100005,inf=0x3f3f3f3f;
int T,n,m,k,d[N],x,y;
int main(){
    for(cin>>T;T;T--){
        memset(d,inf,sizeof(d));
        cin>>n>>m>>k;
        d[k]=0;
        while(m--){
            scanf("%d%d",&x,&y);
            int p=d[x],q=d[y];
            d[x]=min(q,p+1);
            d[y]=min(p,q+1);
        }
        for(int i=1;i<=n;i++)
            cout<<(d[i]==inf?-1:d[i])<<" \n"[i==n];
    }
    return 0;
}