#include <cstdio>
#include <cstring>
#include <algorithm>
#define il __inline__ __attribute__((always_inline))
#define cs const
using namespace std;
typedef long long ll;
typedef cs int& ci;
#define max_n 100000
int ans[max_n+1];
il void test(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    memset(ans,127,sizeof(ans));
    ans[k]=0;
    for(int u,v,i=m; i; --i){
        scanf("%d%d",&u,&v);
        int x=ans[u],y=ans[v];
        ans[u]=min(x+1,y),ans[v]=min(y+1,x);
//        printf("%d %d\n",ans[u],ans[v]);
    }
    for(int i=1; i<n; ++i)
        if(ans[i]<=m)
            printf("%d ",ans[i]);
        else
            printf("-1 ");
        if(ans[n]<=m)
            printf("%d\n",ans[n]);
        else
            printf("-1\n");
}
int main(){
    int t;
    for(scanf("%d",&t); t; --t,test());
    return 0;
}