#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1e5 + 6;
const int inf = 1e9 + 7;
struct node
{
    int ne,to;
    int w;
}a[MAXN<<1];
int head[MAXN],cnt = 0;
void add(int x,int y,int w = 0){
    a[++cnt].ne = head[x];
    head[x] = cnt;
    a[cnt].to = y;
    a[cnt].w = w;
}
struct No
{
    int x;
    int idx;
    No(int x = 0,int idx = 0):x(x),idx(idx){}
    bool operator < (const No a)    const
    {return x < a.x;}
};
int dis[MAXN];
bool vis[MAXN];
void dijk(int k)
{
    priority_queue<No> que;
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(No(k,0));
    
    vis[k] = 1;
    dis[k] = 0;
    while(!que.empty())
    {
        No t = que.top();
        que.pop();
        
        vis[t.idx] = 1;
        for(int i = head[t.idx];i;i = a[i].ne)
        {
            int to = a[i].to;
            if(vis[to])    continue;
            if(dis[to] > dis[t.idx] + a[i].w)
            {
                dis[to] = dis[t.idx] + a[i].w;
                que.push(No(to,dis[to]));
            }
        }
    }
}
int ans[MAXN];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i = 1;i <= n;i++)    ans[i] = inf;
        
        ans[k] = 0;
        for(int i = 0;i < m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            if(ans[x] == inf && ans[y] == inf && x != k && y != k)    continue;
            
            int k1 = ans[x];
            int k2 = ans[y];
            ans[x] = min(k1 + 1,k2);
            ans[y] = min(k2 + 1,k1);
        }
        for(int i = 1;i <= n;i++)
        printf("%d%c",ans[i] == inf ? -1:ans[i]," \n"[i == n]);
    }
    return 0;
}