#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int n,m;
int dp[M];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int K;
        scanf("%d %d %d",&n,&m,&K);
        for(int i=1;i<=n;i++)dp[i]=1e9;
        dp[K]=0;
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            int x=dp[a],y=dp[b];
            dp[b]=min(dp[b]+1,x);
            dp[a]=min(dp[a]+1,y);
        }
        for(int i=1;i<=n;i++){
            printf("%d%c",dp[i]>=1e9?-1:dp[i],i==n?'\n':' ');
        }
    }
    return 0; 
}