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

#define DISTANCE 6

std::vector<int> bfs (std::vector<std::list<int> > graph, int graph_size, int start)
{
        // Create arrays to keep distances and to mark visited nodes
        std::vector<bool> visited (graph_size + 1);
        std::vector<int>  distance (graph_size + 1);
        // Set default values
        for(int i = 0; i <= graph_size; i++)
        {
            distance[i] = -1;
            visited[i] = false;
        }

        std::queue<int> queue;

        visited[start]  = true;
        distance[start] = 0;

        queue.push(start);
        while (!queue.empty())
        {
            int current_vert = queue.front();
            queue.pop();
            std::list<int> lst = graph[current_vert];   // list of nodes, adjacent to current_vert
            // Traverse all the adjacent nodes
            for (std::list<int>::iterator it = lst.begin(); it != lst.end(); it++)
            {
                int adjacent = *it;
                if(!visited[adjacent])
                {
                    visited[adjacent] = true;
                    distance[adjacent] = distance[current_vert] + DISTANCE;
                    queue.push(adjacent);
                }
            }
        }
        return distance;
}

int main()
{
    int ntests = 0, vertices = 0, edges = 0;

    std::cin >> ntests;
    for(int i = 0; i < ntests; i++)
    {
        std::cin >> vertices >> edges;
        std::vector<std::list<int> > graph;
        // Create adjacency list
        for(int i = 0; i <= vertices; ++i)
            graph.push_back(std::list<int>());

        // Insert edges into adjacency list
        for(int i = 0; i < edges; ++i) {
            int x, y;
            std::cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        int start;      // start vertex
        std::cin >> start;

        // Calculate vector of distances
        std::vector<int> distance = bfs (graph, vertices, start);

        // Print shortest distances from start vertex to every other vertices
        for(int i = 1; i <= vertices; i++) {
            if (i != start) {
                std::cout << distance[i] << " ";
            }
        }
        std::cout << std::endl;
    }
}