#include<bits/stdc++.h>
#define reg register
using namespace std;
int T,n,m,k,fy=-1;
int u[100005],v[100005];
int f[100005],s[100005];

int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}

int main(){
    T=read();
    while(T--){
        n=read(),m=read(),k=read();
        for(int i=1;i<=m;i++) u[i]=read(),v[i]=read();
        for(int i=1;i<=n;i++) f[i]=-1,s[i]=0;
        f[k]=0;
        for(int i=1;i<=m;i++){
            int P=f[u[i]],Q=f[v[i]];
            if(P!=-1||Q!=-1){
                if(P==-1) f[u[i]]=Q+i-s[v[i]],f[v[i]]=Q+i-1-s[v[i]];
                else if(Q==-1) f[v[i]]=P+i-s[u[i]],f[u[i]]=P+i-1-s[u[i]];
                else{
                    f[u[i]]=max(Q+i-s[v[i]],P+i-1-s[u[i]]);
                    f[v[i]]=max(Q+i-1-s[v[i]],P+i-s[u[i]]);
                }
            }
            s[v[i]]=s[u[i]]=i;
        }
        for(int i=1;i<=n;i++) if(f[i]!=-1) f[i]=f[i]+m-s[i];
        for(int i=1;i<=n;i++){
            if(f[i]!=-1) printf("%d",m-f[i]);
            else printf("%d",fy);
            if(i!=n) putchar(' ');
        }
        puts("");
    }

    return 0;
}