#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'bfs' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER m
#  3. 2D_INTEGER_ARRAY edges
#  4. INTEGER s
#

class Node:
    def __init__(self, val):
        self.val = val
        self.visited = False
        self.neighbors = []
    def __repr__(self):
        return str(self.val)
    
    def __str__(self):
        return str({"node":self.val, "neighbors":self.neighbors, "visted":self.visited})
    def add_neighbor(self, neighbor):
        if neighbor.val != self.val and neighbor.val not in self.neighbors :
            self.neighbors.append(neighbor.val)

def bfs(n, m, edges, s):
    # Write your code here
    #### step one construct the graph structure
    graph = {}
    # init the graph with nodes with no edges
    for i in range(n):
        node = i +1
        graph[node] = Node(node)
    # add edges to the graph
    for edge in edges:
        n1,n2 = edge
        n1, n2 = graph[n1], graph[n2]
        n1.add_neighbor(n2)
        n2.add_neighbor(n1)
    # print(graph)
    
    #### step 2 calculate distances from the graph datastructure
    cost = 6
    queue = [s] # start off with the start node
    distances = [-1] * n # init all distances with -1
    distances[s-1] = 0 # the start node has a distance of zero 
    while queue:
        node = queue.pop(0)
        node = graph[node]
        if node.visited:
            continue # move on to the next item in the queue
        node.visited=True
        for neighbor in node.neighbors:
            queue.append(neighbor)
            neighbor = graph[neighbor]
            # assumes that the graph nodes ids start with 1 and are sequential 
            # updates distances
            current_node_idx = node.val - 1
            neighbor_node_idx= neighbor.val -1
            # only update distance if it hasn't been updated already
            # this is for the case when I have 1-2 and also 2-1
            if distances[neighbor_node_idx] == -1:
                distances[neighbor_node_idx] = distances[current_node_idx] + cost
            
            # print("current node idx",current_node_idx)
            # print("neighbor node idx",neighbor_node_idx)
            # print("distances list", distances)
            # print("current node",node)
            # print("neighbornode",neighbor)
            # print(queue)
    distances.pop(s-1) # pop the index of the start node
    # print(distances)
    return distances
            
        

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input().strip())

    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        m = int(first_multiple_input[1])

        edges = []

        for _ in range(m):
            edges.append(list(map(int, input().rstrip().split())))

        s = int(input().strip())

        result = bfs(n, m, edges, s)

        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')

    fptr.close()