def bfs(start, graph):
    visited = set()
    queue = []
    queue.append(start)
    dist = 6
    results = {}
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)
            for i in graph[node]:
                if i not in results and i != start:
                    results[i] = dist
            dist += 6
    return results

t = int(input())
for z in range(t):
    n, m = [int(x) for x in input().split()]
    graph = {}
    for i in range(n):
        graph[i + 1] = set()

    for i in range(0, m):
        a, b = [int(x) for x in input().split()]
        graph[a].add(b)
        graph[b].add(a)

    s = int(input())
    x = bfs(s, graph)

    for i in range(1, n + 1):
        if i not in x and i != s:
            x[i] = -1

    for i in range(1, n + 1):
        if i != s:
            print(x[i], end=' ')
    print()