import collections

class Graph(object):
    def __init__(self, numNodes):
        self.n = numNodes
        self.connected = {}

    def connect(self, node1, node2):
        if node1 not in self.connected:
            self.connected[node1] = set()
        if node2 not in self.connected:
            self.connected[node2] = set()
        self.connected[node1].add(node2)
        self.connected[node2].add(node1)

    def find_all_distances(self, start):
        visited = [False for _ in range(self.n)]
        distances = [-1 for _ in range(self.n)]
        queue = collections.deque()
        queue.append(start)
        visited[start] = True
        distances[start] = 0

        while len(queue):
            popped = queue.popleft()
            for path in self.connected[popped]:
                if not visited[path]:
                    visited[path] = True
                    distances[path] = distances[popped]+6
                    queue.append(path)

        print " ".join([str(dist) for dist in distances if dist != 0])

t = input()
for i in range(t):
    n,m = [int(x) for x in raw_input().split()]
    graph = Graph(n)
    for i in xrange(m):
        x,y = [int(x) for x in raw_input().split()]
        graph.connect(x-1,y-1)
    s = input()
    graph.find_all_distances(s-1)