#include <bits/stdc++.h>
using namespace std;

const int N=1010;

vector<int> g[11][N];
int n, m, t, source, dist[N];

void bfs (int start, int x)
{
    queue<int> q;
    q.push(start);
    while (!q.empty())
    {
        int xt=q.front();
        q.pop();
        for (int i=0;i<g[x][xt].size();i++)
        {
            int u=g[x][xt][i];
            if (u!=start && !dist[u])
            {
                dist[u]=dist[xt]+1;
                q.push(u);
            }
        }
    }
}

int main()
{
    cin >> t;
    while (t--)
    {
        scanf ("%d%d", &n, &m);
        for (int i=0;i<m;i++)
        {
            int a, b;
            scanf ("%d%d", &a, &b);
            g[t][a].push_back(b);
            g[t][b].push_back(a);
        }
        scanf ("%d", &source);
        bfs (source, t);
        for (int i=1;i<=n;i++)
        {
            if (i==source) continue;
            if (dist[i]) printf ("%d ", dist[i]*6);
            else printf ("-1 ");
        }
        printf ("\n");
        memset (dist, 0, sizeof dist);
    }

    return 0;
}