def bfs(graph, start):
    queue = []
    visited = set()
    distances = {}
    queue.append(start)
    
    for node in graph:
        distances[node] = -1
    distances[start] = 0
    
    while queue:
        cur = queue.pop()
        if cur in visited:
            continue
        visited.add(cur)
        for neighbor in graph[cur]:
            if neighbor not in visited:
                queue.append(neighbor)
                if distances[neighbor] == -1:
                    distances[neighbor] = distances[cur] + 6
    del distances[start]
    return distances

n_queries = int(input())

for _ in range(n_queries):
    graph = {}
    n,m = list(map(int,input().split()))

    #init graph by points
    for _ in range(n):
        graph[_+1] = []

    for _ in range(m):
        edge = list(map(int,input().split()))
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    start = int(input())
    distances = bfs(graph,start)
    print(*distances.values(), sep=' ')