#include <iostream>
#include <vector>
#include <queue>

#define INF (1 << 29)

using namespace std;

struct grafo{
    vector < vector <int> > adj;
    int nodos, aristas, inicial;

    void leer(){
        cin>>nodos>>aristas;
        adj.resize(nodos+1);
        for(int cont=0;cont<aristas;cont++){
            int n1,n2;
            cin>>n1>>n2;
            adj[n1].push_back(n2);
            adj[n2].push_back(n1);
        }
        cin>>inicial;
    }

    void BFS(){
        vector<int>distancia((nodos+1),INF);
        distancia[inicial]=0;
        queue<int>cola;
        cola.push(inicial);
            while(cola.size()>0){
                int aux=cola.front();
                cola.pop();
                for(int cont2=0;cont2<adj[aux].size();cont2++){
                    if(distancia[aux]+6<distancia[adj[aux][cont2]]){
                        distancia[adj[aux][cont2]]=distancia[aux]+6;
                        cola.push(adj[aux][cont2]);
                    }
                }

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

int main()
{
    int casos;
    cin>>casos;
    for(int i=0;i<casos;i++){
        grafo g;

        g.leer();

        g.BFS();
    }

    return 0;
}