BFS

bfs

def bfs(g, start):
    distance = [0] * len(g)
    queue = []
    queue.append(start - 1)
    distance[start - 1] = 0
    while len(queue) != 0:
        current = queue.pop(0)
        for i in g[current]:
            if distance[i] == 0:
                distance[i] = distance[current] + 6
                queue.append(i)
    return distance




t = int(input())
for i in range(t):
    v, e = input().split()
    GRAPH = {}
    for i in range(int(v)):
        GRAPH[i] = set()
    for j in range(int(e)):
        u, q = [int(x) for x in input().split()]
        GRAPH[u - 1].add(q - 1)
    start = int(input())
    visited = bfs(GRAPH, start)
    for j in range(len(visited)):
        if j == start - 1:
            continue
        if visited[j] == 0:
            print("-1", end=' ')
        else:
            print(visited[j], end=' ')
    print()