#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int T;

 int n, m, s;

 int d[maxn];

 vector<int> G[maxn];

 void bfs()

 {

     queue<int> Q;

     Q.push(s);

     set<int> t1,t2;

     set<int>::iterator it;

     for(int i=;i<=n;i++)  if(i!=s)  t1.insert(i);

     while(!Q.empty())

     {

         int u=Q.front(); Q.pop();

         for(int i=;i<G[u].size();i++)

         {

             int v=G[u][i];

             if(!t1.count(v))  continue;

             t1.erase(v);  //删去u点不能到达的点

             t2.insert(v);  //将这些点放入t2*下一次使用

         }

         for(it=t1.begin();it!=t1.end();it++)  //这些点都是u能到达的

         {

             d[*it]=d[u]+;

             Q.push(*it);

         }

         t1.swap(t2);  //t2中存储的是还没到达过的点

         t2.clear();

     }

     bool flag=true;

     for(int i=;i<=n;i++)

     {

         if(i==s)  continue;

         if(!flag)  printf(" ");

         if(flag)   flag=false;

         if(d[i]==-)  printf("-1");

         else printf("%d",d[i]);

     }

     printf("\n");

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)  G[i].clear();

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         scanf("%d",&s);

         memset(d,-,sizeof(d));

         d[s]=;

         bfs();

     }

     return ;

 }