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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(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)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) f|=IO=='-';
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

bool Mbe;
const int N=1e6+10,INF=1e9+10,P=998244353;

int n,m,k;
int dp[N];

bool Med;
int main(){ 
    rep(_,1,rd()) {
        n=rd(),m=rd(),k=rd();
        rep(i,1,n) dp[i]=INF;
        dp[k]=0;
        rep(i,1,m) {
            int u=rd(),v=rd();
            int a=dp[u],b=dp[v];
            dp[u]=min(a+1,b);
            dp[v]=min(b+1,a);
        }
        rep(i,1,n) printf("%d%c",dp[i]==INF?-1:dp[i]," \n"[i==n]);
    }
}