#include <bits/stdc++.h>

using namespace std;

int f[1001000]; 
int main() {
  int T;
  scanf("%d",&T);
  while (T--) {
    int n,m,k;
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++) {
      f[i]=1e9; 
    } 
    f[k]=0; 
    for (int i=1;i<=m;i++) {
      int u,v;
      scanf("%d %d",&u,&v);
      int X=f[u],Y=f[v];
      f[u]=min(X+1,Y);
      f[v]=min(Y+1,X); 
    }
    for (int i=1;i<=n;i++) {
      if (f[i]==1e9) printf("-1");
      else printf("%d",f[i]); 
      if (i!=n) printf(" "); 
    }
    printf("\n"); 
  }
  return 0; 
}