class Graph(object):
    def __init__(self, n):
        self.n = n
        self.distances = [-1 for _ in xrange(n)]
        self.neighbors = {i:set() for i in xrange(n)}

    def connect(self, x, y):
        self.neighbors[x].add(y)
        self.neighbors[y].add(x)

    def find_all_distances(self, src):
        self.distances[src] = 0
        q = [src]
        while q:
            curr = q.pop(0)
            for neighbor in self.neighbors[curr]:
                if self.distances[neighbor] == -1:
                    self.distances[neighbor] = self.distances[curr] + 6
                    q.append(neighbor)

        print ' '.join(str(d) for i, d in enumerate(self.distances) if i != src)


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)