#include<cstdio>

#include<set>

#include<queue>

#include<cstring>

using namespace std;

const int N = 2e5 + 5;

set <int> G[N],a,b;

int ans[N];

void bfs(int s)

{

    queue <int> q;

    set<int>::iterator it;

    q.push(s);

    while(!q.empty())

    {

        int t = q.front();

        q.pop();

        for(it = G[t].begin() ;it != G[t].end() ;it++)

        {

            if(a.count(*it))//如果当前还未寻找到

            {

                a.erase(*it);//该点本次可以寻找到，从a中删去

                b.insert(*it);//本次仍不能找到

            }

        }

        for(it = a.begin() ;it != a.end() ;it++)

        {

            ans[*it] = ans[t] + 1;

            q.push(*it);

        }

        a.swap(b);//b传递给a

        b.clear();//...

    }

    for(it = a.begin() ;it != a.end() ;it++)

        ans[*it] = -1;//剩余的点

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m,num = 0;

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

        memset(ans,0,sizeof(ans));

        a.clear();

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

            G[i].clear();

        while(m--)

        {

            int u,v;

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

            G[u].insert(v);

            G[v].insert(u);

        }

        int s;

        scanf("%d",&s);

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

            if(i != s) a.insert(i);

        bfs(s);

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

        {

            if(i != s)

            {

                num++;

                if(num != n-1)

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

                else

                    printf("%d\n",ans[i]);

            }

        }

    }

    return 0;

}