#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF (1 << 29)

vector<vector<int> > ady;

vector<int> BFS(int cantidad, int inicial){///1
    vector<int> dist(cantidad, INF);
    queue<int> cola;

    cola.push(inicial); dist[inicial] = 0;
    while(cola.size()) {                                       ///2
        int nodo = cola.front();
        cola.pop();

        for(int i=0; i<ady[nodo].size(); i++)
        {                                       ///3
            int vecino = ady[nodo][i];
            if(dist[nodo]+6<dist[vecino])
            {                                   ///4
                dist[vecino] = dist[nodo] + 6;
                cola.push(vecino);
            }                                     ///-4
        }                                       ///-3
    }                                           ///-2

    return dist;
}                                               ///-1

int main(){
    int n,m,u,v,q,s;
    cin>>q;

    for(int i=0;i<q;i++){
        cin>>n>>m;
        ady.resize(n);
        for(int j=0;j<m;j++){
            cin>>u>>v;
            ady[u].push_back(v); ady[v].push_back(u);
        }
        cin>>s;

        vector<int> distancia=BFS(n,s);

        for(int j=0;j<n;j++){
            if(j!=s){
                if(distancia[j] = INF){cout<<"-1 ";
                }
                else{
                    cout<<distancia[j]<<" ";
                }
            }

        }
        cout<<endl;
    }







    return 0;
}