#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MN 100000

using std::min;
using std::swap;

int id[MN+5],f[MN+5],u[MN+5],v[MN+5];

void solve(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
    }
    for(int i=1;i<=n;i++)
        id[i] = i;
    for(int i=m;i>=1;i--)
        swap(id[u[i]],id[v[i]]);
    memset(f,0x7f,sizeof(f));
    f[id[k]] = 0;
    for(int i=1;i<=m;i++){
        int u = ::u[i];
        int v = ::v[i];
        f[id[u]] = min(f[id[u]],f[id[v]]+1);
        f[id[v]] = min(f[id[v]],f[id[u]]+1);
        swap(id[u],id[v]);
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",f[i]==0x7f7f7f7f?-1:f[i]," \n"[i==n]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
}