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


const int N=1e5+100;

int f[N];

int main() {

    int T,n,m,k,i,a,b;
    scanf("%d",&T);
    
    while (T--) {
        scanf("%d%d%d",&n,&m,&k);

        for (i=1;i<=n;i++)
            f[i]=i==k?0:1<<30;

        while (m--) {
            scanf("%d%d",&a,&b);
            swap(f[a],f[b]);
            f[a]=min(f[a],f[b]+1);
            f[b]=min(f[b],f[a]+1);
        }

        for (i=1;i<=n;i++)
            printf("%d%c",f[i]==1<<30?-1:f[i]," \n"[i==n]);
    }
return 0;
}