#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define fgx cerr<<"-------------"<<endl
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
void dbg(){cerr<<endl;}
template<typename A,typename... B>void dbg(A x,B... y){cerr<<x<<" ";dbg(y...);}
#define debug(...) cerr<<#__VA_ARGS__<<"=",dbg(__VA_ARGS__)
int f[1000000];
int main()
{    int t; cin>>t;
    while(t--) {
        int n,m,k,x,y; scanf("%d%d%d",&n,&m,&k);
        for(rint i=1;i<=n;i++) f[i]=1e9;
        f[k]=0;
        for(rint i=1;i<=m;i++) {
            scanf("%d%d",&x,&y);
            int fx=f[x],fy=f[y];
            f[x]=min(fy,fx+1);
            f[y]=min(fx,fy+1);
        }
        for(rint i=1;i<=n;i++)
        if(f[i]>m) cout<<"-1"<<" \n"[i==n];
        else cout<<f[i]<<" \n"[i==n];
    }
    return 0;
}