#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,k;
int A[150000],B[150000];
int ans[150000];

int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<m;i++){
            scanf("%d %d",A+i,B+i);
            A[i]--,B[i]--;
        }
        for(int i=0;i<n;i++)ans[i]=0x3f3f3f3f;
        ans[k-1]=0;
        for(int i=0;i<m;i++){
            int a=A[i],b=B[i];
            int t=ans[a];
            ans[a]=min(ans[a]+1,ans[b]);
            ans[b]=min(ans[b]+1,t);
        }
        for(int i=0;i<n;i++){
            if(ans[i]>1000000)ans[i]=-1;
            printf("%d%c",ans[i],i==n-1?'\n':' ');
        }
    }
}