BFS

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
enum color {WHITE,GRAY,BLACK};

vector<ll> vertex_color;
vector<ll> _distance;
vector<ll> parent;
vector<vector<ll>> adjList;
ll N,M;

void BFS(ll N,ll s)
{
    vertex_color.clear();
    vertex_color.resize(N+1);
    _distance.clear();
    _distance.resize(N+1);
    parent.clear();
    parent.resize(N+1);

    queue<ll> q;
    for(ll i = 1; i <= N; i++)
    {
        vertex_color[i] = WHITE;
        _distance[i] = -1;
        parent[i] = 0;
    }
    vertex_color[s] = GRAY;
    _distance[s] = 0;
    parent[s] = 0;
    q.push(s);

    while(!q.empty())
    {
        ll u = q.front();
        q.pop();
        for(ll i = 0; i < adjList[u].size(); i++)
        {
            ll v = adjList[u][i];
            if(vertex_color[v] == WHITE)
            {
                vertex_color[v] = GRAY;
                _distance[v] = _distance[u]+6;
                parent[v] = u;
                q.push(v);
            }
        }
        vertex_color[u] = BLACK;
    }
}
int main()
{
    int q;
    cin >> q;
    while(q--)
    {
        ll s;
        cin >> N >> M;
        adjList.resize(N+1);
        for(int i = 0; i < M; i++)
        {
            int u,v;
            cin >> u >> v;
            adjList[u].push_back(v);
            adjList[v].push_back(u);
        }
        cin >> s;
        BFS(N,s);
        for(int i = 1; i <= N; i++)
        {
            if(i!=s)
                cout << _distance[i] << " ";
        }
        cout << endl;
        for(int i = 0; i <= N; i++)
            adjList[i].clear();
        adjList.clear();
    }
    return 0;
}