#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100005;
int f[N];
int n,m,k;
const int INF = 0x3f3f3f3f;
int main(){
    int T;
    int i, j, u, v;
    cin>>T;
    while(T--){
        memset(f, 0x3f, sizeof f);
        scanf("%d%d%d",&n,&m,&k);
        f[k] = 0;
        for(i=1;i<=m;i++){
            scanf("%d%d",&u, &v);
            int newu, newv;
            newu = min(f[u]+1, f[v]);
            newv = min(f[u], f[v]+1);
            f[u] = newu;
            f[v] = newv;
        }
        for(i=1;i<n;i++)printf("%d ",f[i]>=INF?-1:f[i]);
        printf("%d\n",f[i]>=INF?-1:f[i]);
    }
}