#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;


int main() 
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    
    int T;
    cout<<"Nhap so do thi: ";
    cin>>T;
    
    while(T--)
    {
        int N,M;
        cout<<"Nhap so node va so lien ket: ";
        cin>>N>>M;
        vector<int> v[N+1];
        int s;        
        queue<int> q;
        int dist[N+1]={0};
        bool marked[N+1]={0};
        
        for(int i=0;i<M;i++)
        {
            int x,y;
            cout<<"Nhap 2 node co lien ket: ";
            cin>>x>>y;            
            v[x].push_back(y);
            v[y].push_back(x);
        }
        cout<<"Nhap node co bat dau: ";
        cin>>s;        
        q.push(s);
        /* bảng bool nhằm đánh dấu các giá trị đã đi qua */
        marked[s] = true;
        
        while(!q.empty())
        {
            int t = q.front(); // t = phần tử đầu của queue
            q.pop();           // xóa phần tử đầu của queue
            
            for(int i=0;i<v[t].size();i++)
            {
                
                // t là giá trị của phần tử đầu của queue đã bị pop
                // t là node bắt đầu
                if( !marked[v[t][i]])
                {
                    q.push(v[t][i]);
                    dist[v[t][i]] += dist[t]+1;
                    marked[v[t][i]] = true;
                }
            }
        }
        cout << "Dap an: ";
        for(int i =1;i<=N;i++)
        {
            if(i != s)
            {
                if( dist[i] != 0){
                    cout<<dist[i]*6<<" ";
                }
                else
                {
                    cout<<-1<<" ";
                }
            }
        }        
        cout<<endl;
    }
    return 0;
}