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=' ')

import java.io.*
import java.util.*
import java.util.Scanner.*

fun main(args: Array<String>) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT.
         */
    val query = readln().toInt()
    
    for(i in 0 until query){
        val c = HashMap<Int, HashSet<Int>>()    
        val q: Queue<Int> = LinkedList()
        val nm = readln().split(" ")
        val n = nm[0].toInt()
        val m = nm[1].toInt()
        
        for(i in 0 until m){
            val uv =  readln().split(" ")
            val u = uv[0].toInt()
            val v = uv[1].toInt()
            if(c[u] == null){
                c[u] = HashSet()
            }  
            if(c[v] == null){
                c[v] = HashSet()
            }
            c[u]!!.add(v) 
            c[v]!!.add(u) 
        }
        
        val s = readln().trim().toInt()
        
        val visited = Array(n){0}
        
        q.offer(s)
        
        while(q.isNotEmpty()){
            val node = q.peek()
            c[node]?.forEach{
                if (visited[it - 1] == 0) {
                    visited[it - 1] = visited[node - 1] + 6
                    q.offer(it) 
                } 
            }
            q.poll()  
        }
        
        val sb = StringBuilder()
        for (i in visited.indices){
            val v = visited[i]
            if(i +1 != s ) {
                if (v > 0){
                    sb.append(v)
                } else {
                    sb.append("-1")
                }
                if(i != visited.lastIndex) {
                    sb.append(" ") 
                } 
            } 
        } 
        
        println(sb.toString())
    }
}

#!/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()

function bfs(n, m, edges, s) {
    let graph = {}
    // fill the graph with empty sets (equivalent to Python's defaultdict(set))
    Array(n+1).fill(null).forEach((v, i) => graph[i] = new Set())
    
    let result = []
    
    // Construct graph double linked (undirected)
    for (let [n1, n2] of edges) {
        graph[n1].add(n2)
        graph[n2].add(n1)
    }
    
    // For node i = 1...n calculate distance from the start node to 'i'
    for (let i = 1; i <= n; i++) {
        if (i == s) continue // skip start node in the result array
        
        let queue = []
        // We use distances array also as visited array
        let distances = Array(n+1).fill(null).map(_ => -1) // start distance as -1 for all
        distances[s] = 0 // starting node has distance of 0
        queue.push(s)
        
        // BFS LOOP ----------------------------
        while (queue.length > 0) {
            let node = queue.shift()
            for (let neighbor of graph[node]) {
                if (distances[neighbor] === -1) {
                    queue.push(neighbor)
                    // each distance is 6 more than the previous node
                    distances[neighbor] = distances[node] + 6
                    if (neighbor === i) { // if the target node i is reached
                        queue = [] // set the queue to empty to break the outer loop
                        break // no need to continue inner loop either
                    }
                }
            }
        }
        result.push(distances[i] || -1)
    }
    return result
}