#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long

const int maxn=1e5+10;

/**
能否15/20/30写完

没有分析样例啊……

不要气lei，接着高效写

**/

//struct node
//{
//    int d;
//    node * to;
//}*e[maxn];
//
//int step[maxn],q[maxn];
//bool vis[maxn];

int f[maxn];

int op(int a,int b)
{
    if (b==-1)
        b=-1;
    else
        b++;

    if (a==-1)
        return b;
    if (b==-1)
        return a;
    return min(a,b);
}

int main()
{

    int t,n,m,x,y,d,pos,i,head,tail;
    int vx,vy;
//    node *p;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d%d",&n,&m,&pos);

//        for (i=1;i<=n;i++)
//        {
//            e[i]=NULL;
//            vis[i]=0;
//            step[i]=-1;
//        }
//
////        memset(vis,0,sizeof(vis));
//
//        while (m--)
//        {
//            scanf("%d%d",&x,&y);
//
//            p=new node();
//            p->d=y;
//            p->to=e[x];
//            e[x]=p;
//
//            p=new node();
//            p->d=x;
//            p->to=e[y];
//            e[y]=p;
//
//            if (pos==x)
//                pos=y;
//            else if (pos==y)
//                pos=x;
//        }
//
//        head=0,tail=1;
//        q[1]=pos;
//        vis[pos]=1,step[pos]=0;
//
//        while (head<=tail)
//        {
//            head++;
//            d=q[head];
//
//            p=e[d];
//            while (p)
//            {
//                if (!vis[p->d])
//                {
//                    tail++;
//                    q[tail]=p->d;
//                    vis[p->d]=1;
//                    step[p->d]=step[d]+1;
//                }
//                p=p->to;
//            }
//        }

        ///停留在k的最少步数
        for (i=1;i<=n;i++)
            f[i]=-1;
        f[pos]=0;

        while (m--)
        {
            scanf("%d%d",&x,&y);

            vx=f[x],vy=f[y];

            ///to x
            f[x]=op(vy,vx); ///vx+1
            f[y]=op(vx,vy); ///vy+1

        }



        for (i=1;i<=n;i++)
        {
//            printf("%d",step[i]);
            printf("%d",f[i]);

            ///change
            if (i==n)
                printf("\n");
            else
                printf(" ");
        }

//        while (1)
//        {
//            p=e[pos];
//            while (p)
//            {
//
//            }
//        }
//
//        for (i=1;i<=;i++)
//        {
//
//        }

    }



    return 0;
}