#include<iostream>

#include<algorithm>

#include<cstring>

#include<set>

#include<queue>

#include<cstdio>

using namespace std;

const int maxn=200500;

const int inf=0x3f3f3f3f;

struct Edge

{

    int next;

    int to;

}edge[maxn];

int head[maxn];

int visit[maxn];

int dist[maxn];

int cnt;

int n,m;

int start;

set<int>s;

void add(int u,int v)

{

    edge[cnt].next=head[u];edge[cnt].to=v;head[u]=cnt++;

}

void init()

{

    memset(head,-1,sizeof(head));

    cnt=0;

}

void bfs(int u)

{

    fill(dist+1,dist+1+n,inf);

    queue<int>q;

    q.push(u);

    set<int>s1,s2;//s2保存未拓展的点，既还没有到达可能由其它点中转的点；

    dist[u]=0;

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

        if(i!=u)

        s1.insert(i);//先把所有点加入

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        for(int i=head[now];i!=-1;i=edge[i].next)

        {

            int v=edge[i].to;

            if(!s1.count(v))//如果这个点被直接连边，那么这条边不算

                continue;

            s1.erase(v);

            s2.insert(v);//把这个点扔到没法拓展的点里面

        }

        for(set<int>::iterator it=s1.begin();it!=s1.end();it++)

        {

            q.push(*it);

            dist[*it]=dist[now]+1;

        }

        s1.swap(s2);

        s2.clear();

    }

}

int main()

{

    int tt;

    int u,v;

    while(scanf("%d",&tt)!=EOF)

    {

        while(tt--)

        {

            init();

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

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

            {

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

                add(u,v);add(v,u);

            }

            scanf("%d",&start);

        bfs(start);//开始

        int cot=0;

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

        {

            if(i==start)

                continue;cot++;

            if(dist[i]==inf)

                cout<<-1;

            else

                cout<<dist[i];

            if(cot<=n-2)

                cout<<" ";

        }

        cout<<endl;

        }

    }

}