Consider an undirected graph where each edge weighs 6 units.  Each of the nodes is labeled consecutively from 1 to n.

You will be given a number of queries.  For each query, you will be given a list of edges describing an undirected graph.  After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS).  Return an array of distances from the start node in node number order.  If a node is unreachable, return $-1$ for that node.  

Example 

The following graph is based on the listed inputs:  

$n=5$  // number of nodes 

$m=3$  // number of edges 

$edges=[1,2],[1,3],[3,4]$ 

$s=1$  // starting node  

All distances are from the start node $1$.  Outputs are calculated for distances to nodes $2$ through $5$: $[6,6,12,-1]$.  Each edge is $\boldsymbol{6}$ units, and the unreachable node $5$ has the required return distance of $-1$.  

Function Description  

Complete the bfs function in the editor below.    If a node is unreachable, its distance is $-1$.  

bfs has the following parameter(s):  

int n: the number of nodes  
int m: the number of edges  
int edges[m][2]: start and end nodes for edges
int s: the node to start traversals from  

Returns 

int[n-1]:  the distances to nodes in increasing node number order, not including the start node (-1 if a node is not reachable)  

Input Format

The first line contains an integer $\textit{q}$, the number of queries. 
Each of the following $\textit{q}$ sets of lines has the following format:

The first line contains two space-separated integers $n$ and $m$, the number of nodes and edges in the graph.  
Each line $\boldsymbol{i}$ of the $m$ subsequent lines contains two space-separated integers, $\mbox{u}$ and $v$, that describe an edge between nodes $\mbox{u}$ and $v$.  
The last line contains a single integer, $\boldsymbol{\mathrm{~S~}}$, the node number to start from.

Constraints

$1\leq q\leq10$  
$2\leq n\leq1000$  
$1\leq m\leq\frac{n\cdot(n-1)}{2}$  
$1\leq u,v,s\leq n$  

Sample Input
2
4 2
1 2
1 3
1
3 1
2 3
2

Sample Output
6 6 -1
-1 6

Explanation

We perform the following two queries:

The given graph can be represented as: 

where our start node, $\boldsymbol{\mathrm{~S~}}$, is node $1$. The shortest distances from $\boldsymbol{\mathrm{~S~}}$ to the other nodes are one edge to node $2$, one edge to node $3$, and an infinite distance to node $4$ (which it is not connected to). We then return an array of distances from node $\mbox{I}$ to nodes $2$, $3$, and $4$ (respectively): $[6,6,-1]$.  

The given graph can be represented as: 

where our start node, $\boldsymbol{\mathrm{~S~}}$, is node $2$. There is only one edge here, so node $1$ is unreachable from node $2$ and node $3$ has one edge connecting it to node $2$. We then return an array of distances from node $2$ to nodes $1$, and $3$ (respectively): $[-1,6]$.  

Note: Recall that the actual length of each edge is $\boldsymbol{6}$, and we return $-1$ as the distance to any node that is unreachable from $\boldsymbol{\mathrm{~S~}}$.

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
class Graph(object):

	def __init__(self, N, M):
		(self.N, self.M) = (N, M)
		self.alist = {key: list() for key in range(1, N + 1)}
		for index in range(M):
			(t, h) = [int(value) for value in input().split()]
			self.alist[t].append(h)
			self.alist[h].append(t)

	def bfs(self, source):
		distances = {key: -1 for key in range(1, self.N + 1)}
		to_explore = set([source])
		current_distance = 0
		while to_explore:
			next_nodes = set()
			for tnode in to_explore:
				if distances[tnode] == -1:
					distances[tnode] = current_distance
					next_nodes.update(self.alist[tnode])
			to_explore = next_nodes
			current_distance += 1
		self.distances = distances

	def answer(self, source):
		self.bfs(source)
		for index in range(1, N + 1):
			if index == source:
				continue
			elif self.distances[index] == -1:
				print(-1, end=' ')
			else:
				print(6 * self.distances[index], end=' ')
		print()
T = int(input())
for index in range(T):
	(N, M) = [int(value) for value in input().split()]
	graph = Graph(N, M)
	source = int(input())
	graph.answer(source)


def find(V, N, S):
	dist = [-1 for x in range(N)]
	visited = [False for x in range(N)]
	Q = [S]
	depth = 1
	dist[S] = 0
	while Q:
		if not visited[Q[0]]:
			for x in V[Q[0]]:
				if dist[x] == -1:
					dist[x] = dist[Q[0]] + 6
				else:
					dist[x] = min(dist[x], dist[Q[0]] + 6)
				Q.append(x)
			visited[Q[0]] = True
		del Q[0]
	del dist[S]
	for x in dist:
		print(x, end=' ')
	print()
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	V = [set() for x in range(N)]
	for i in range(M):
		(X, Y) = (int(x) - 1 for x in input().split())
		V[X].add(Y)
		V[Y].add(X)
	find(V, N, int(input()) - 1)


from collections import defaultdict, deque

def breadth_first_search(S, N, G, L=1):
	E = defaultdict(int)
	C = {}
	for n in range(1, N + 1):
		C[n] = -1
	E[S] += 1
	C[S] = 0
	Q = deque([S])
	while Q:
		n = Q.popleft()
		for h in G[n]:
			if E[h] == 0:
				E[h] += 1
				C[h] = C[n] + L
				Q.append(h)
	return C

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		G = defaultdict(set)
		for _ in range(M):
			E = [int(i) for i in input().split()]
			G[E[0]].add(E[1])
			G[E[1]].add(E[0])
		S = int(input())
		D = breadth_first_search(S, N, G, 6)
		print(' '.join((str(D[n]) for n in range(1, N + 1) if n != S)))
main()


import queue

def bfs(graph, s, v, path):
	q = queue.Queue()
	q.put(s)
	v[s] = 1
	while q.empty() == False:
		j = q.get()
		for i in graph[j]:
			if v[i] == 0:
				v[i] = 1
				path[i] = path[j] + 6
				q.put(i)

def main():
	for i in range(int(input())):
		(n, e) = input().split()
		(n, e) = (int(n), int(e))
		graph = []
		for k in range(n):
			graph.append([])
		for j in range(e):
			(a, b) = input().split()
			(a, b) = (int(a), int(b))
			graph[a - 1].append(b - 1)
			graph[b - 1].append(a - 1)
		s = int(input())
		v = [0] * n
		path = [0] * n
		bfs(graph, s - 1, v, path)
		o = ''
		for x in range(len(path)):
			if x == s - 1:
				continue
			if path[x] == 0:
				o += str(-1) + ' '
			else:
				o += str(path[x]) + ' '
		print(o)
main()


def bfs(graph, start, N):
	dist = [-1] * (N + 1)
	prev = [-1] * (N + 1)
	dist[0] = 0
	dist[start] = 0
	queue = [start]
	visited = set()
	counter = 0
	while queue:
		vertex = queue.pop(0)
		if vertex not in visited:
			visited.add(vertex)
			if vertex in graph.keys():
				S = list(graph[vertex] - visited)
				for s in S:
					if prev[s] == -1:
						prev[s] = vertex
				queue.extend(graph[vertex] - visited)
			if vertex != start:
				dist[vertex] = dist[prev[vertex]] + 6
	return ' '.join(map(str, list(filter(0 .__ne__, dist))))
T = int(input())
for i in range(0, T):
	graph = {}
	inp = input().split()
	N = int(inp[0])
	M = int(inp[1])
	for j in range(0, M):
		inp = input().split()
		edge1 = int(inp[0])
		edge2 = int(inp[1])
		if edge1 in graph:
			graph[edge1].add(edge2)
		else:
			graph[edge1] = {edge2}
		if edge2 in graph:
			graph[edge2].add(edge1)
		else:
			graph[edge2] = {edge1}
	S = int(input())
	print(bfs(graph, S, N))


def create_nodes(number_of_nodes):
	return [i for i in range(1, number_of_nodes + 1)]

def make_link(G, node1, node2):
	if node1 not in G:
		G[node1] = {}
	G[node1][node2] = 1
	if node2 not in G:
		G[node2] = {}
	G[node2][node1] = 1

def find_all_distance(G, s_node):
	open_list = [s_node]
	distances_from_start = {}
	distances_from_start[s_node] = 0
	while open_list:
		cur_node = open_list.pop(0)
		if cur_node not in G:
			continue
		for neighbour in G[cur_node]:
			if neighbour not in distances_from_start:
				distances_from_start[neighbour] = distances_from_start[cur_node] + 6
				open_list.append(neighbour)
	return distances_from_start
no_tests = int(input())
for i in range(no_tests):
	[no_nodes, no_edges] = input().split()
	nodes = create_nodes(int(no_nodes))
	G = {}
	for j in range(int(no_edges)):
		[node1, node2] = input().split()
		make_link(G, int(node1), int(node2))
	s_node = int(input())
	distance_from_start = find_all_distance(G, s_node)
	for node in nodes:
		if node == s_node:
			continue
		if node in distance_from_start:
			print(distance_from_start[node], end=' ')
		else:
			print(-1, end=' ')
	print('')


def bfs(s, d):
	q = [[s, 0]]
	visited = {}
	for i in range(1, n + 1):
		visited[i] = 0
	res = [-1 for i in range(n)]
	res[s - 1] = 0
	while q:
		u = q.pop()
		if visited[u[0]] == 0:
			visited[u[0]] = 1
			res[u[0] - 1] = 6 * u[1]
			for i in d[u[0]]:
				if visited[i] == 0:
					q.insert(0, [i, u[1] + 1])
	return res
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	d = {}
	for j in range(1, n + 1):
		d[j] = []
	for j in range(m):
		(n1, n2) = [int(k) for k in input().split()]
		d[n1].append(n2)
		d[n2].append(n1)
	s = int(input())
	res = bfs(s, d)
	del res[res.index(0)]
	print(' '.join(map(str, res)))


def BFS(s, n, adj):
	frontier = [s]
	level = {s: 0}
	parent = {s: None}
	i = 1
	while frontier:
		next = []
		for u in frontier:
			for v in adj[u]:
				if v not in level:
					level[v] = i
					parent[v] = u
					next.append(v)
		frontier = next
		i += 1
	ans = ''
	for i in range(1, n + 1):
		if i not in level:
			ans += '-1 '
		elif i == s:
			pass
		else:
			ans += str(level[i] * 6) + ' '
	print(ans)
adj = {}
t = int(input())
for i in range(t):
	inp = input()
	inp = inp.split(' ')
	n = int(inp[0])
	m = int(inp[1])
	for j in range(1, n + 1):
		adj[j] = []
	for j in range(m):
		inp = input()
		inp = inp.split(' ')
		adj[int(inp[0])].append(int(inp[1]))
		adj[int(inp[1])].append(int(inp[0]))
	s = int(input())
	BFS(s, n, adj)


class Graph:

	def __init__(self, n):
		self.data = [[] for i in range(n)]

	def add_edge(self, a, b):
		a -= 1
		b -= 1
		self.data[a].append(b)
		self.data[b].append(a)

	def adj(self, n):
		return self.data[n]
from collections import deque

def run():
	(n, e) = list(map(int, input().strip().split(' ')))
	graph = Graph(n)
	for i in range(e):
		graph.add_edge(*list(map(int, input().strip().split(' '))))
	start = int(input()) - 1
	marked = [False] * n
	marked[start] = True
	distTo = [-1] * n
	distTo[start] = 0
	q = deque([start])
	while q:
		node = q.pop()
		nearest = graph.adj(node)
		for n in nearest:
			if marked[n]:
				continue
			marked[n] = True
			distTo[n] = 6 + distTo[node]
			q.appendleft(n)
	distTo.remove(0)
	print(' '.join(map(str, distTo)))
t = int(input())
for i in range(t):
	run()


from collections import deque

def bfs(graph, start, end):
	queue = deque()
	seen = {}
	if end in graph[start]:
		return 6
	for key in graph[start].keys():
		seen[key] = True
		queue.append((key, 6))
	while len(queue) > 0:
		(key, dist) = queue.popleft()
		if end in graph[key]:
			return dist + 6
		for nkey in graph[key].keys():
			if nkey in seen:
				continue
			seen[nkey] = True
			queue.append((nkey, dist + 6))
	return -1
tests = int(input())
c = 0
while c < tests:
	c += 1
	[nodes, edges] = [int(x) for x in input().split(' ')]
	graph = {}
	for idx in range(1, nodes + 1):
		graph[idx] = {}
	e = 0
	while e < edges:
		e += 1
		[idx, jdx] = [int(x) for x in input().split(' ')]
		graph[idx][jdx] = True
		graph[jdx][idx] = True
	s = int(input())
	line = ''
	for idx in range(1, nodes + 1):
		if idx == s:
			continue
		line += str(bfs(graph, s, idx)) + ' '
	print(line[:-1])


from collections import deque

class Vertex:

	def __init__(self, id):
		self.id = id
		self.visited = False
		self.score = -1
		self.edges = []

	def __str__(self):
		return str(self.score)

	def addEdge(self, to):
		if to not in self.edges:
			self.edges.append(to)

def bfs(g, v):
	v.visited = True
	v.score = 0
	q = deque([])
	q.append(v)
	while len(q) > 0:
		for n in [graph[x] for x in q[0].edges]:
			if not n.visited:
				n.score = q[0].score + 6
				n.visited = True
				q.append(n)
		q.popleft()
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	graph = {n: Vertex(n) for n in range(1, N + 1)}
	for m in range(M):
		(x, y) = map(int, input().split())
		graph[x].addEdge(y)
		graph[y].addEdge(x)
	S = int(input())
	bfs(graph, graph[S])
	graph.pop(S)
	print(' '.join(map(str, graph.values())))


def bfs(g, v, r):
	q = [r]
	while q != []:
		x = q.pop(0)
		for i in g[x]:
			if v[i] == -1:
				q.append(i)
				v[i] = v[x] + 6
	return
for t in range(int(input())):
	(n, m) = [int(i) for i in input().split(' ')]
	g = [[] for i in range(n + 1)]
	for k in range(m):
		(u, v) = [int(i) for i in input().split(' ')]
		g[u].append(v)
		g[v].append(u)
	r = int(input())
	v = [-1] * (n + 1)
	v[r] = 0
	bfs(g, v, r)
	s = ''
	for i in range(1, n + 1):
		if i != r:
			s += str(v[i]) + ' '
	print(s)


def bfstree(g, root):
	q = [root]
	while q:
		node = q.pop(0)
		print(node, end=' ')
		for x in g.get(node, []):
			q.append(x)

def bfs(g, v, s):
	q = [s]
	while q:
		node = q.pop(0)
		for i in g[node]:
			if v[i] == -1:
				q.append(i)
				v[i] = v[node] + 6
t = int(input())
for j in range(t):
	(n, m) = [int(i) for i in input().split(' ')]
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = [int(i) for i in input().split(' ')]
		g[x].append(y)
		g[y].append(x)
	s = int(input())
	visited = [-1] * (n + 1)
	visited[s] = 0
	bfs(g, visited, s)
	sx = ''
	for i in range(1, n + 1):
		if i != s:
			sx += str(visited[i]) + ' '
	print(sx)


T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	nodes = []
	for i in range(N):
		nodes.append(set())
	marked = [False] * N
	dist = [-1] * N
	for _ in range(M):
		(s, t) = [int(x) - 1 for x in input().split()]
		nodes[s].add(t)
		nodes[t].add(s)
	s = int(input()) - 1
	dist[s] = 0
	q = [s]
	while q:
		x = q.pop(0)
		for y in nodes[x]:
			if not marked[y]:
				marked[y] = True
				q.append(y)
				dist[y] = dist[x] + 6
	dist.pop(s)
	print(*dist)


def get_min_node(distances, unvisited):
	min_node = None
	for node in unvisited:
		if not min_node or distances[node] < distances[min_node]:
			min_node = node
	return min_node

def dijkstra(graph, num_of_nodes, start):
	distances = [float('inf')] * (num_of_nodes + 1)
	unvisited = list(range(1, num_of_nodes + 1))
	distances[start] = 0
	current_node = start
	while len(unvisited) > 0:
		unvisited.remove(current_node)
		if current_node in graph.keys():
			for node in graph[current_node]:
				if node in unvisited:
					new_distance = distances[current_node] + 6
					if new_distance < distances[node]:
						distances[node] = new_distance
		current_node = get_min_node(distances, unvisited)
	return distances
num_of_tests = int(input())
for i in range(num_of_tests):
	graph = {}
	graph_attr = input().split()
	num_of_nodes = int(graph_attr[0])
	num_of_edges = int(graph_attr[1])
	for j in range(num_of_edges):
		edge = input().split()
		x = int(edge[0])
		y = int(edge[1])
		if x not in graph.keys():
			graph[x] = []
		graph[x].append(y)
		if y not in graph.keys():
			graph[y] = []
		if x not in graph[y]:
			graph[y].append(x)
	start = int(input())
	result_list = dijkstra(graph, num_of_nodes, start)
	del result_list[start]
	for d in result_list[1:]:
		if d == float('inf'):
			print(-1, end=' ')
		else:
			print(d, end=' ')
	print('')


def shortest_reach(G, S):
	R = [-1 for i in range(len(G))]
	R[S] = 0
	Visited = [False for i in range(len(G))]
	Q = []
	Q.append((S, G[S]))
	while len(Q) > 0:
		node = Q.pop(0)
		s = node[0]
		vs = node[1]
		for v in vs:
			Visited[v] = True
			if R[v] == -1:
				R[v] = R[s] + 6
			else:
				R[v] = min(R[v], R[s] + 6)
		for v in vs:
			uv = []
			for x in G[v]:
				if not Visited[x]:
					uv.append(x)
			if len(uv) > 0:
				Q.append((v, uv))
	return R
T = int(input())
for x in range(T):
	l = input().split()
	(N, M) = (int(l[0]), int(l[1]))
	A = [[] for i in range(N)]
	for i in range(M):
		l = input().split()
		(v1, v2) = (int(l[0]) - 1, int(l[1]) - 1)
		if v2 not in A[v1]:
			A[v1].append(v2)
		if v1 not in A[v2]:
			A[v2].append(v1)
	for (i, v) in enumerate(A):
		A[i] = sorted(A[i])
	S = int(input()) - 1
	path = shortest_reach(A, S)
	del path[S]
	print(' '.join(map(str, path)))


import heapq
for i in range(int(input())):
	(V, E) = map(int, input().split())
	edge = [[] for _ in range(V)]
	for _ in range(E):
		(fr, to) = map(lambda x: int(x) - 1, input().split())
		edge[fr].append(to)
		edge[to].append(fr)
	s = int(input()) - 1
	dist = [float('inf')] * V
	dist[s] = 0
	pque = [(0, s)]
	while pque:
		(now_dist, now_node) = heapq.heappop(pque)
		if dist[now_node] < now_dist:
			continue
		for next_node in edge[now_node]:
			if now_dist + 6 < dist[next_node]:
				dist[next_node] = now_dist + 6
				heapq.heappush(pque, (dist[next_node], next_node))
	print(*[-1 if x == float('inf') else x for x in dist if x])


import fileinput
input_list = []
for line in fileinput.input():
	input_list.append([x for x in line.strip().split(' ')])
T = int(input_list[0][0])
cases = input_list[1:]
(i, el) = (0, 6)

def grapher(edges, S):
	(ed, graph) = ([], {S: []})
	for pair in edges:
		(node1, node2) = (pair[0], pair[1])
		if node1 not in graph:
			graph[node1] = [node2]
		elif node2 not in graph[node1]:
			graph[node1].append(node2)
		if node2 not in graph:
			graph[node2] = [node1]
		elif node1 not in graph[node2]:
			graph[node2].append(node1)
	queue = [S]
	while queue:
		k = queue.pop(0)
		for x in graph[k]:
			if x not in queue:
				queue.append(x)
			graph[x].remove(k)
	return graph

def calc(key, queue, deg):
	deg += 1
	q = []
	if key in queue:
		return deg
	else:
		for x in queue:
			if x in graph:
				q += graph[x]
		if q:
			deg = calc(key, q, deg)
		else:
			return -1
	return deg
for t in range(T):
	(N, M) = (int(cases[i][0]), int(cases[i][1]))
	S = cases[i + 1 + M][0]
	edges = cases[i + 1:i + 1 + M]
	graph = grapher(edges, S)
	res = ''
	for x in range(1, N + 1):
		key = str(x)
		if key not in graph:
			res += '-1 '
		elif key != S:
			dist = calc(key, graph[S], 0)
			res += str(dist * el) + ' ' if dist > 0 else str(dist) + ' '
	print(res.strip())
	i += 2 + M


def solve():
	(n, m) = [int(x) for x in input().split()]
	adjList = [[] for x in range(n)]
	for i in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		adjList[a].append(b)
		adjList[b].append(a)
	S = int(input())
	S -= 1
	ans = [-1] * n
	ans[S] = 0
	Q = [S]
	while len(Q) > 0:
		node = Q[0]
		Q = Q[1:]
		for i in adjList[node]:
			if i != -1 and ans[i] == -1:
				ans[i] = ans[node] + 6
				Q.append(i)
	for i in range(n):
		if ans[i] != 0:
			print('' + str(ans[i]) + ' ', end='')
	print()
tc = int(input())
for i in range(tc):
	solve()


import math
from queue import Queue

class Node:
	visited = False

	def __init__(self, name, N):
		self.name = name
		self.adjNode = []

	def insertAdj(self, adj):
		self.adjNode.append(adj)

	def __lt__(self, other):
		return self.name < other.name

	def __str__(self):
		return str(self.name)

	def __repr__(self):
		return str(self)

def BFS(s, N):
	dist = [-1] * (N + 1)
	dist[s.name] = 0
	q = Queue()
	q.put(s)
	s.visited = True
	while not q.empty():
		x = q.get()
		for y in x.adjNode:
			if y.visited is False:
				dist[y.name] = dist[x.name] + 6
				q.put(y)
				y.visited = True
	return dist

def main():
	T = int(input())
	for i in range(T):
		(N, M) = map(int, input().split())
		nodeList = [None] * (N + 1)
		edge = {}
		for j in range(M):
			(x, y) = map(int, input().split())
			if x > N or y > N:
				continue
			if nodeList[x] is None:
				xNode = Node(x, N)
			else:
				xNode = nodeList[x]
			if nodeList[y] is None:
				yNode = Node(y, N)
			else:
				yNode = nodeList[y]
			if (x, y) in edge.keys() or (y, x) in edge.keys():
				continue
			edge[x, y] = True
			xNode.insertAdj(yNode)
			yNode.insertAdj(xNode)
			nodeList[x] = xNode
			nodeList[y] = yNode
		S = int(input())
		if nodeList[S] is None:
			sNode = Node(S, N)
			nodeList[S] = sNode
		else:
			sNode = nodeList[S]
		dist = BFS(sNode, N)
		for x in dist[1:]:
			if x != 0:
				print(x, end=' ')
		print()
main()


G = []
D = []
C = []

def BFS(v):
	Q = [v]
	while len(Q) > 0:
		v = Q.pop(0)
		for u in G[v]:
			if not C[u]:
				D[u] = D[v] + 6
				Q.append(u)
				C[u] = 1
		C[v] = 2
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	G = [[] for _ in range(n + 1)]
	D = [-1] * (n + 1)
	C = [0] * (n + 1)
	for _ in range(m):
		(x, y) = list(map(int, input().split()))
		G[x].append(y)
		G[y].append(x)
	s = int(input())
	D[s] = 0
	BFS(s)
	print(' '.join(list(map(str, D[1:s] + D[s + 1:]))))


from queue import Queue
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split(' ')))
	graph = {v: {'edges': [], 'distance': float('inf')} for v in range(1, n + 1)}
	for i in range(m):
		(x, y) = list(map(int, input().split(' ')))
		graph[x]['edges'].append(y)
		graph[y]['edges'].append(x)
	starting_point = int(input())
	graph[starting_point]['distance'] = 0
	q = Queue()
	q.put(starting_point)
	while not q.empty():
		current_node = q.get()
		distance_to_current_node = graph[current_node]['distance']
		for neighbor in graph[current_node]['edges']:
			distance_to_neighbor_from_current_node = distance_to_current_node + 6
			if distance_to_neighbor_from_current_node < graph[neighbor]['distance']:
				graph[neighbor]['distance'] = distance_to_neighbor_from_current_node
				q.put(neighbor)
	print(' '.join([str(graph[v]['distance']) if graph[v]['distance'] != float('inf') else '-1' for v in range(1, n + 1) if v != starting_point]))


for _ in range(int(input())):
	(N, M) = list(map(int, input().split(' ')))
	V = {}
	for v in range(1, N + 1):
		V[v] = []
	for m in range(M):
		(x, y) = list(map(int, input().split(' ')))
		V[x].append(y)
		V[y].append(x)
	S = int(input())
	Q = [S]
	D = {}
	D[S] = 0
	while len(Q) > 0:
		d = D[Q[0]]
		u = Q[0]
		Q = Q[1:]
		for v in V[u]:
			if not v in D:
				D[v] = d + 6
				Q.append(v)
	res = []
	for x in V.keys():
		if not x in D:
			res.append('-1')
		elif D[x] > 0:
			res.append(str(D[x]))
	print(' '.join(res))


def read_input(dic, dist):
	num = [int(i) for i in input().split()]
	for i in range(1, num[0] + 1):
		dic[i] = []
		dist[i] = 0
	for i in range(0, num[1]):
		line = [int(i) for i in input().split()]
		dic[line[0]].append(line[1])
		dic[line[1]].append(line[0])
	return int(input())

def do_the_bfs(dic, dist, s):
	que = [s]
	while que:
		cur = que.pop(0)
		child = dic[cur]
		curd = dist[cur]
		for i in child:
			if i != s and dist[i] == 0:
				dist[i] = curd + 6
				que.append(i)

def my_print(dic, dist, s):
	out = ''
	for i in dic.keys():
		if i != s:
			if dist[i] == 0:
				out += '-1 '
			else:
				out += str(dist[i]) + ' '
	print(out)
n = int(input())
for i in range(0, n):
	dic = {}
	dist = {}
	s = read_input(dic, dist)
	do_the_bfs(dic, dist, s)
	my_print(dic, dist, s)


T = int(input())
for _ in range(T):
	EDGE = []
	DISTANCE = []

	def init_edge(N):
		for i in range(N + 1):
			EDGE.append([])
			DISTANCE.append(-1)

	def insert_edge(node1, node2):
		if node2 not in EDGE[node1]:
			EDGE[node1].append(node2)
		if node1 not in EDGE[node2]:
			EDGE[node2].append(node1)

	def BFS(start_node, DISTANCE):
		STACK = []
		STACK.append(start_node)
		DISTANCE[start_node] = 0
		NOTVISITED = list(range(1, N + 1))
		NOTVISITED.remove(start_node)
		while len(STACK) > 0:
			curr = STACK[0]
			del STACK[0]
			for ele in EDGE[curr]:
				if ele in NOTVISITED:
					STACK.append(ele)
					DISTANCE[ele] = DISTANCE[curr] + 6
					NOTVISITED.remove(ele)
	(N, M) = tuple(map(int, input().split()))
	init_edge(N)
	for _ in range(M):
		(node1, node2) = tuple(map(int, input().split()))
		insert_edge(node1, node2)
	start_node = int(input())
	BFS(start_node, DISTANCE)
	for i in range(1, N + 1):
		if i != start_node:
			print(DISTANCE[i], end=' ')
	print()


def walk_graph(numnodes, edges, startnode):
	nodes = [-1] * (numnodes + 1)
	nodes[startnode] = 0
	next_nodes = [startnode]
	while next_nodes:
		these_nodes = next_nodes
		next_nodes = []
		for n in these_nodes:
			for e in edges[n]:
				if nodes[e[0]] == -1 or nodes[e[0]] > nodes[n] + e[1]:
					nodes[e[0]] = nodes[n] + e[1]
					next_nodes.append(e[0])
	return nodes

def main():
	WEIGHT = 6
	T = int(input())
	for i in range(T):
		(N, M) = tuple(map(int, input().split()))
		edges = [set() for i in range(N + 1)]
		for m in range(M):
			(x, y) = tuple(map(int, input().split()))
			edges[x].add((y, WEIGHT))
			edges[y].add((x, WEIGHT))
		S = int(input())
		nodes = walk_graph(N, edges, S)
		nodes.pop(S)
		print(' '.join([str(nodes[n]) for n in range(1, len(nodes))]))
main()


class Node:

	def __init__(self, ID):
		self.id = ID
		self.mates = {}
		self.dist = 1000000000000000
		self.prev = None
		self.ok = True
		self.prev = []

	def __repr__(self):
		return 'Node-' + str(self.id)

class Edge:

	def __init__(self, node1, node2, dist=None):
		self.dist = 0
		if dist is None:
			self.dist = 6
		else:
			self.dist = dist
		self.n1 = GRAPH[node1 - 1]
		self.n2 = GRAPH[node2 - 1]
		self.connect()

	def connect(self):
		p = 1
		if self.n2 in self.n1.mates:
			p = 0
		if p:
			self.n2.mates[self.n1] = self.dist
			self.n1.mates[self.n2] = self.dist

def getkey(node):
	return node.dist

def algorithm(graph, source):
	source.dist = 0
	Q = []
	for v in graph:
		Q.append(v)
	while len(Q) != 0:
		Q = sorted(Q, key=getkey)
		u = Q[0]
		Q = Q[1:]
		for v in u.mates:
			alt = u.dist + u.mates[v]
			if alt < v.dist:
				v.dist = alt
				v.prev.append(u)
	for node in graph:
		if node.dist == 1000000000000000:
			node.dist = 0
			node.dist = -1
test = int(input())
a = 0
while a < test:
	pl = list(map(int, input().split()))
	node_no = pl[0]
	edge_no = pl[1]
	GRAPH = [None] * node_no
	for i in range(node_no):
		GRAPH[i] = Node(i + 1)
	EDGES = [None] * edge_no
	for i in range(edge_no):
		nodes = list(map(int, input().split()))
		EDGES[i] = Edge(nodes[0], nodes[1])
	start = int(input(''))
	start = GRAPH[start - 1]
	algorithm(GRAPH, start)
	for node in GRAPH:
		if node is not start:
			print(node.dist, end=' ')
	print(sep=' ')
	a += 1


import collections
import io

class Node:

	def __init__(self, index):
		self.index = index
		self.relationship_indexes = set()
		self.distance = -1
		self.previous_node = None

def traverse(start_node, graph):
	index_queue = collections.deque()
	index_queue.appendleft(start_node.index)
	current_node = graph[0]
	while index_queue:
		tmp_node = graph[index_queue.pop()]
		tmp_node.previous_node = current_node
		current_node = tmp_node
		for edge_index in current_node.relationship_indexes:
			edge_node = graph[edge_index]
			if not edge_node.previous_node:
				edge_node.previous_node = current_node
				edge_node.distance = max(0, current_node.distance) + 6
				index_queue.appendleft(edge_index)
T = int(input().strip())
for test_case in range(T):
	(N, M) = [int(_) for _ in input().split()]
	graph = [Node(i) for i in range(N + 1)]
	for (node_a, node_b) in [[int(x) for x in input().split()] for i in range(M)]:
		graph[node_a].relationship_indexes.add(node_b)
		graph[node_b].relationship_indexes.add(node_a)
	S = int(input())
	start_node = graph[S]
	traverse(start_node, graph)
	print(' '.join((str(_.distance) for _ in graph[1:] if _ is not start_node)))


EDGE_WEIGHT = 6

class Graph:

	def __init__(self, num_nodes):
		self.num_nodes = num_nodes
		self.node_to_edges = {}
		for node in range(1, num_nodes + 1):
			self.node_to_edges[node] = set()

	def add_edge(self, node1, node2):
		self.add_directed_edge(node1, node2)
		self.add_directed_edge(node2, node1)

	def add_directed_edge(self, start, end):
		self.node_to_edges[start].add(end)

	def bfs_distances(self, start):
		distances = [-1] * self.num_nodes
		seen = {start}
		queue = [(start, 0)]
		while len(queue) > 0:
			(current_node, current_level) = queue.pop(0)
			self.__update_queue(queue, current_node, current_level, seen)
			if current_level != 0:
				distances[current_node - 1] = current_level * EDGE_WEIGHT
		distances.pop(start - 1)
		return distances

	def __update_queue(self, queue, current_node, current_level, seen):
		for node in self.node_to_edges[current_node]:
			if node not in seen:
				queue.append((node, current_level + 1))
				seen.add(node)

	def __str__(self):
		return str(self.node_to_edges)

def read_tuple():
	return [int(x) for x in input().split()]
num_tests = int(input())
for _ in range(num_tests):
	(n, m) = read_tuple()
	graph = Graph(n)
	for _ in range(m):
		graph.add_edge(*read_tuple())
	starting_node = int(input())
	distances = graph.bfs_distances(starting_node)
	print(' '.join((str(d) for d in distances)))


import sys
from pprint import pprint

def print_result(result, start):
	res = ''
	for i in range(len(result)):
		if i != start - 1:
			res += str(result[i]) + ' '
	return res

def calculate(graph, n_of_nodes, start):
	visited = [False for i in range(n_of_nodes)]
	result = [-1 for i in range(n_of_nodes)]
	nodes = []
	nodes.append((start, 0))
	while len(nodes) > 0:
		current = nodes.pop(0)
		if visited[current[0] - 1]:
			continue
		visited[current[0] - 1] = True
		node = graph.get(current[0])
		if node != None:
			for adjacent in node:
				nodes.append((adjacent, current[1] + 6))
		if current[0] != start:
			result[current[0] - 1] = current[1]
	return result

def add_node(graph, node1, node2):
	node = graph.get(node1)
	if node != None:
		node.add(node2)
	else:
		graph[node1] = set()
		graph[node1].add(node2)
file = sys.stdin
number_of_test = int(file.readline())
for i in range(number_of_test):
	graph = {}
	(nodes, edges) = file.readline().split(' ')
	nodes = int(nodes)
	edges = int(edges)
	for j in range(edges):
		(node1, node2) = file.readline().split(' ')
		node1 = int(node1)
		node2 = int(node2)
		node = graph.get(node1)
		add_node(graph, node1, node2)
		add_node(graph, node2, node1)
	start = int(file.readline())
	result = calculate(graph, nodes, start)
	print(print_result(result, start))


T = int(input())
for t in range(T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	edge_set = [[] for i in range(N)]
	for i in range(M):
		(e1, e2) = input().split()
		e1 = int(e1) - 1
		e2 = int(e2) - 1
		edge_set[e1].append(e2)
		edge_set[e2].append(e1)
	node = int(input()) - 1
	L = [[node]]
	level = 0
	node_dist = [-1 for i in range(N)]
	node_dist[node] = 0
	while L[level]:
		L.append([])
		for node_cur in L[level]:
			for node_next in edge_set[node_cur]:
				if node_dist[node_next] == -1:
					L[level + 1].append(node_next)
					node_dist[node_next] = 6 * (level + 1)
		level = level + 1
	outstr = ''
	for i in range(N):
		if i != node:
			outstr += str(node_dist[i])
			outstr += ' '
	print(outstr)


class vertex:

	def __init__(self, id, distance):
		self.id = id
		self.distance = distance
		self.parent = None
		self.adj = []
T = int(input())
for t in range(0, T):
	var = input().split()
	(N, M) = (int(var[0]), int(var[1]))
	vertices = []
	for n in range(0, N):
		vertices.append(vertex(n + 1, -1))
	for m in range(0, M):
		var = input().split()
		(ver1, ver2) = (int(var[0]), int(var[1]))
		vertices[ver1 - 1].adj.append(ver2)
		vertices[ver2 - 1].adj.append(ver1)
	source = int(input())
	vertices[source - 1].distance = 0
	need_to_visit = [source]
	current_level = 1
	while len(need_to_visit) != 0:
		next = []
		for u in need_to_visit:
			for v in vertices[u - 1].adj:
				if vertices[v - 1].distance == -1:
					vertices[v - 1].distance = current_level
					next.append(v)
					vertices[v - 1].parent = u
		need_to_visit = next
		current_level += 1
	out = ''
	for n in range(0, N):
		if n == source - 1:
			continue
		index = n
		if vertices[index].distance != -1:
			out += str(vertices[index].distance * 6)
		else:
			out += str(vertices[index].distance)
		out = out + ' '
	print(out)


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, m) = [int(_) for _ in input().split()]
	g = defaultdict(list)
	for j in range(m):
		(x, y) = [int(_) for _ in input().split()]
		g[x].append(y)
		g[y].append(x)
	s = int(input())
	d = [n + 1] * (n + 1)
	d[s] = 0
	active = [s]
	reached = [False] * (n + 1)
	reached[s] = True
	while active:
		new_active = []
		for x in active:
			for y in g[x]:
				if d[y] > d[x] + 1:
					d[y] = d[x] + 1
					new_active.append(y)
		active = new_active
	out = ''
	for x in range(1, n + 1):
		if x == s:
			continue
		if d[x] == n + 1:
			print(-1, end=' ')
		else:
			print(6 * d[x], end=' ')
	print(' ')


from collections import defaultdict
readinput = lambda x: [int(y) for y in x.split()]
for testcase in range(int(input())):
	(N, M) = readinput(input())
	neighbours = defaultdict(list)
	dist = defaultdict(int)
	visited = defaultdict(bool)
	for _ in range(M):
		(src, dst) = readinput(input())
		neighbours[src - 1].append(dst - 1)
		neighbours[dst - 1].append(src - 1)
	start = int(input()) - 1
	queue = [start]
	visited[start] = True
	curr_dist = 6
	while queue:
		next_level = []
		for node in queue:
			for neighbour in neighbours[node]:
				if not visited[neighbour]:
					visited[neighbour] = True
					dist[neighbour] = curr_dist
					next_level.append(neighbour)
		queue = next_level
		curr_dist += 6
	for i in range(N):
		if i == start:
			continue
		if dist[i] == 0:
			print(-1, end=' ')
		else:
			print(dist[i], end=' ')
	print()


from collections import deque

def bfs_shortest_path(graph, s):
	paths = [-1] * vert_count
	fringe = deque([(s, 0)])
	while len(fringe) > 0:
		(s, length) = fringe.popleft()
		if paths[s] == -1:
			paths[s] = length
			for i in graph[s]:
				fringe.append((i, length + 1))
	return paths
for j in range(int(input())):
	(vert_count, edge_count) = [int(i) for i in input().split()]
	graph = [[] for i in range(vert_count)]
	for i in range(edge_count):
		(x, y) = [int(i) - 1 for i in input().split()]
		graph[x].append(y)
		graph[y].append(x)
	s = int(input()) - 1
	for i in bfs_shortest_path(graph, s):
		if i != 0:
			print(i if i == -1 else i * 6, end=' ')
	print()


def getneighbout(top, ad_matrix, n):
	l = []
	for k in range(1, n + 1):
		if ad_matrix[top - 1][k] == 1 or ad_matrix[k - 1][top] == 1:
			l.append(k)
	return l
t = int(input())
for each in range(t):
	(n, m) = [int(i) for i in input().strip().split()]
	edges = []
	for i in range(m):
		(x, y) = [int(i) for i in input().strip().split()]
		edges.append((x, y))
	s = int(input())
	ad_matrix = []
	for node1 in range(1, n + 1):
		row = [0]
		for node2 in range(1, n + 1):
			row.append(-1)
		ad_matrix.append(row)
	for (a, b) in edges:
		ad_matrix[a - 1][b] = 1
	visited = []
	distance = []
	for i in range(n + 1):
		visited.append(0)
		distance.append(0)
	queue = []
	queue.append(s)
	mul = 6
	while len(queue) != 0:
		top = queue[0]
		queue.remove(queue[0])
		for neigh in getneighbout(top, ad_matrix, n):
			if visited[neigh] == 0:
				distance[neigh] += distance[top] + 6
				queue.append(neigh)
				visited[neigh] = 1
	for i in range(1, len(distance)):
		if i != s:
			if distance[i] != 0:
				print(distance[i], end=' ')
			else:
				print(-1, end=' ')
	print('')


class Node:

	def __init__(self, name):
		self.name = name
		self.connected = set()
		self.distance = -1

	def connect(self, other):
		self.connected.add(other)
		other.connected.add(self)
test_size = int(input().strip())
for i in range(0, test_size):
	test_case = input().strip().split(' ')
	num_of_nodes = int(test_case[0])
	num_of_edges = int(test_case[1])
	nodes = []
	nodes.append(Node('empty'))
	for n in range(1, num_of_nodes + 1):
		nodes.append(Node(n))
	for j in range(0, num_of_edges):
		line = input().strip().split(' ')
		node1 = nodes[int(line[0])]
		node2 = nodes[int(line[1])]
		node1.connect(node2)
	root_name = int(input().strip())
	root = nodes[root_name]
	root.distance = 0
	visited = set()
	queue = []
	queue.append(root)
	visited.add(root)
	while len(queue) > 0:
		out = queue.pop(0)
		for neighbor in out.connected:
			if neighbor not in visited:
				neighbor.distance = out.distance + 6
				visited.add(neighbor)
				queue.append(neighbor)
	print_str = ''
	for i in range(1, num_of_nodes + 1):
		if i != root_name:
			print_str = print_str + str(nodes[i].distance) + ' '
	print(print_str.strip())


import queue

class Graph:
	v = 0
	e = 0

	def __init__(self, V):
		self.v = V
		self.adj = [[] for _ in range(V)]

	def add_edge(self, V, W):
		self.adj[V].append(W)
		self.adj[W].append(V)
		self.e = self.e + 2

	def V(self):
		return self.v

	def E(self):
		return self.e

class BFSClass:
	marked = []
	dist_to = []

	def __init__(self, graph, source):
		self.marked = [False] * graph.V()
		self.dist_to = [None] * graph.V()
		self.source = source
		self.bfs(graph)

	def bfs(self, graph):
		s = self.source
		q = queue.Queue()
		q.put(s)
		dist = 1
		self.marked[s] = True
		self.dist_to[s] = 0
		for a in range(graph.V()):
			while q.empty() == False:
				s = q.get()
				for v in graph.adj[s]:
					if self.marked[v] == False:
						self.dist_to[v] = self.dist_to[s] + 1
						self.marked[v] = True
						q.put(v)
cases = int(input())
for i in range(cases):
	(v, e) = map(int, input().split())
	g = Graph(v)
	for y in range(e):
		(a, b) = map(int, input().split())
		g.add_edge(a - 1, b - 1)
	s = int(input())
	bfs = BFSClass(g, s - 1)
	for x in bfs.dist_to:
		if x == 0:
			continue
		if x == None:
			print(-1, end=' ')
			continue
		print(x * 6, end=' ')
	print()


import sys
T = int(sys.stdin.readline())
for case in range(T):
	[N, M] = [int(X) for X in sys.stdin.readline().split()]
	G = [set() for n in range(N)]
	for m in range(M):
		[s, t] = [int(X) - 1 for X in sys.stdin.readline().split()]
		G[s].add(t)
		G[t].add(s)
	S = int(sys.stdin.readline()) - 1
	distances = [-1 for n in range(N)]
	visiting = [(S, 0)]
	visited = {S}
	while visiting:
		(current, distance) = visiting[0]
		visiting.pop(0)
		distances[current] = distance
		nexts = G[current] - visited
		visited |= nexts
		visiting.extend([(next_, distance + 6) for next_ in nexts])
	distances.pop(S)
	for distance in distances:
		print(distance, end=' ')
	print()


__author__ = 'sr1k4n7h'

class Graph(object):

	def __init__(self, N, M):
		(self.N, self.M) = (N, M)
		self.alist = {key: list() for key in range(1, N + 1)}
		for index in range(M):
			(t, h) = [int(value) for value in input().split()]
			self.alist[t].append(h)
			self.alist[h].append(t)

	def bfs(self, source):
		distances = {key: -1 for key in range(1, self.N + 1)}
		to_explore = set([source])
		current_distance = 0
		while to_explore:
			next_nodes = set()
			for tnode in to_explore:
				if distances[tnode] == -1:
					distances[tnode] = current_distance
					next_nodes.update(self.alist[tnode])
			to_explore = next_nodes
			current_distance += 1
		self.distances = distances

	def answer(self, source):
		self.bfs(source)
		for index in range(1, N + 1):
			if index == source:
				continue
			elif self.distances[index] == -1:
				print(-1, end=' ')
			else:
				print(6 * self.distances[index], end=' ')
		print()
T = int(input())
for index in range(T):
	(N, M) = [int(value) for value in input().split()]
	graph = Graph(N, M)
	source = int(input())
	graph.answer(source)


__author__ = 'Nathan'
t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	edges = {x: [] for x in range(1, n + 1)}
	for j in range(m):
		(n1, n2) = input().split()
		(n1, n2) = (int(n1), int(n2))
		edges[n1].append(n2)
		edges[n2].append(n1)
	unvisited = {x for x in range(1, n + 1)}
	answers = {x: -1 for x in range(1, n + 1)}
	start = int(input())
	unvisited.remove(start)
	node_queue = [(start, 0)]
	del answers[start]
	while node_queue:
		(current_node, current_dist) = node_queue.pop(0)
		for x in edges[current_node]:
			if x in unvisited:
				node_queue.append((x, current_dist + 6))
				unvisited.remove(x)
				answers[x] = current_dist + 6
	for x in answers:
		print(answers[x], end=' ')
	print()


from collections import deque

def bfs(start, adj_map):
	visited = {}
	parent = {}
	visited[start] = True
	parent[start] = None
	Q = deque()
	Q.append(start)
	while len(Q):
		node = Q.popleft()
		if node in adj_map:
			for child in adj_map[node]:
				if child not in visited:
					parent[child] = node
					visited[child] = True
					Q.append(child)
	return parent

def calculate_distance(node, start, parents):
	if node not in parents:
		return -1
	else:
		count = 0
		x = node
		while parents[x]:
			count += 6
			x = parents[x]
		return count
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	adj_map = {}
	nodes = set()
	for _ in range(M):
		(e1, e2) = [int(x) for x in input().split()]
		if e1 in adj_map:
			adj_map[e1].add(e2)
		else:
			adj_map[e1] = set([e2])
		if e2 in adj_map:
			adj_map[e2].add(e1)
		else:
			adj_map[e2] = set([e1])
		nodes.add(e1)
		nodes.add(e2)
	start = int(input())
	if start in nodes:
		nodes.remove(start)
	parents = bfs(start, adj_map)
	dists = []
	for i in range(1, N + 1):
		if i == start:
			continue
		elif i not in nodes:
			dists.append(-1)
		else:
			dists.append(calculate_distance(i, start, parents))
	print(' '.join((str(x) for x in dists)))


from collections import deque
from operator import itemgetter

def create_graph():
	data = input().split()
	num_of_nodes = int(data[0])
	num_of_edges = int(data[1])
	graph = {}
	for x in range(1, num_of_nodes + 1, 1):
		graph[x] = []
	for i in range(num_of_edges):
		data = input().split()
		fro_m = int(data[0])
		to = int(data[1])
		if fro_m in graph[to] or to in graph[fro_m]:
			continue
		else:
			graph[to].append(fro_m)
			graph[fro_m].append(to)
	return graph

def do_level_bfs(graph, start_node):
	d = deque()
	d.appendleft(start_node)
	out = []
	new_level = False
	nodes_in_level = len(graph[start_node])
	nodes_next_level = 0
	temp = d.pop()
	out.append(temp)
	for i in graph[temp]:
		d.appendleft(i)
	while len(d) != 0:
		temp = d.pop()
		if nodes_in_level == 0:
			nodes_in_level = nodes_next_level
			nodes_next_level = 0
			out.append('level complete')
		out.append(temp)
		for i in graph[temp]:
			if i not in out and i not in d:
				nodes_next_level += 1
				d.appendleft(i)
		nodes_in_level -= 1
	return out

def sort_and_print(level_bfs, key_list):
	level_comp_count = 1
	to_sort_by_indices = {}
	for i in level_bfs[1:]:
		if i == 'level complete':
			level_comp_count += 1
			continue
		to_sort_by_indices[i] = 6 * level_comp_count
	key_list = sorted(key_list)
	final_output = []
	for i in key_list:
		if i not in to_sort_by_indices:
			final_output.append('-1')
		else:
			final_output.append(str(to_sort_by_indices[i]))
	print(' '.join(final_output))
num_test = int(input())
for i in range(num_test):
	graph = create_graph()
	start_node = int(input())
	level_bfs = do_level_bfs(graph, start_node)
	key_list = list(graph.keys())
	key_list.remove(start_node)
	sort_and_print(level_bfs, key_list)


for _ in range(int(input())):
	(n, m) = list(map(int, input().strip().split(' ')))
	graph = {}
	for i in range(n):
		graph[i + 1] = []
	for _ in range(m):
		(a, b) = list(map(int, input().strip().split(' ')))
		if b not in graph[a]:
			graph[a].append(b)
		if a not in graph[b]:
			graph[b].append(a)
	start = int(input())
	shortest_paths = [0] * (n + 1)
	queue = [start]
	next_queue = []
	count = 0
	visited = set()
	while queue:
		vertex = queue.pop(0)
		if shortest_paths[vertex] == 0:
			shortest_paths[vertex] = count
			for next in graph[vertex]:
				if shortest_paths[next] == 0:
					next_queue.append(next)
		if not queue:
			queue = next_queue
			next_queue = []
			count += 6
	del shortest_paths[start]
	answer = ''
	for num in shortest_paths[1:]:
		if num == 0:
			answer += str(-1) + ' '
		else:
			answer += str(num) + ' '
	print(answer)


test_cases = int(input().strip())
for test in range(test_cases):
	(nodes, edges) = [int(item) for item in input().strip().split()]
	graph = {node + 1: set() for node in range(nodes)}
	for edge in range(edges):
		(from_, to) = [int(item) for item in input().strip().split()]
		graph[from_].add(to)
		graph[to].add(from_)
	source = int(input().strip())
	node_queue = [source]
	queue_idx = 0
	distances = {source: 0}
	while queue_idx < len(node_queue):
		node = node_queue[queue_idx]
		distance = distances[node] + 6
		queue_idx += 1
		for child in graph[node]:
			if child not in distances:
				node_queue.append(child)
				distances[child] = distance
	print(' '.join((str(distances[j] if j in distances else -1) for j in range(1, nodes + 1) if j != source)))


__author__ = 'pcalg_000'
from collections import deque

def init_nodes(number_of_nodes):
	result = dict()
	for n in range(number_of_nodes):
		result[n + 1] = set()
	return result

def read_edge(graph, new_edge):
	current_edge = [int(val) for val in new_edge.split(' ')]
	graph[current_edge[0]].add(current_edge[1])
	graph[current_edge[1]].add(current_edge[0])

def bfs(start_node, graph):
	search_state = deque([(start_node, 0)])
	visited = set()
	result = dict()
	while len(search_state) > 0:
		(curr_node, dist) = search_state.popleft()
		if curr_node not in visited:
			result[curr_node] = dist
		visited.add(curr_node)
		neighbours = graph[curr_node]
		for neighbour in neighbours:
			if neighbour not in visited:
				search_state.append((neighbour, dist + 6))
	return result

def print_result(start_node, number_of_nodes, distances):
	for n in range(1, number_of_nodes + 1):
		if n != start_node:
			if n in distances:
				print('{0} '.format(distances[n]), end='')
			else:
				print('-1 ', end='')
	print('')
testcases = int(input())
for _ in range(testcases):
	line = [int(n) for n in input().split(' ')]
	number_of_nodes = line[0]
	number_of_edges = line[1]
	graph = init_nodes(number_of_nodes)
	for _ in range(number_of_edges):
		read_edge(graph, input())
	start_node = int(input())
	distances = bfs(start_node, graph)
	print_result(start_node, number_of_nodes, distances)


def bfs(S, N, E):
	dist = {}
	visited = {}
	for i in range(0, N):
		visited[i] = False
		dist[i] = -1
	queue = []
	queue.append(S)
	visited[S] = True
	dist[S] = 0
	while len(queue) != 0:
		u = queue.pop(0)
		for v in E[u]:
			if visited[v] == False:
				queue.append(v)
				dist[v] = dist[u] + 6
				visited[v] = True
	return dist
T = int(input())
for i in range(0, T):
	(N, M) = map(int, input().split(' '))
	E = {}
	for j in range(0, N):
		E[j] = set()
	for j in range(0, M):
		(x, y) = map(int, input().split(' '))
		E[x - 1].add(y - 1)
		E[y - 1].add(x - 1)
	S = int(input())
	dist = bfs(S - 1, N, E)
	del dist[S - 1]
	for k in sorted(dist):
		print(str(dist[k]), end=' ')
	print()


def bfsDist(g, s):
	result = [-1] * len(g)
	result[s] = 0
	q = [s]
	while len(q) > 0:
		v = q[0]
		q = q[1:]
		for neib in g[v]:
			if result[neib] < 0:
				result[neib] = result[v] + 6
				q += [neib]
	return result
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	g = [[] for i in range(n)]
	for __ in range(m):
		(f, t) = [int(x) - 1 for x in input().split()]
		g[f] += [t]
		g[t] += [f]
	s = int(input()) - 1
	r = bfsDist(g, s)
	print(' '.join((str(x) for x in r if x != 0)))


T = int(input())
for _ in range(T):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	adjacency_list = [[] for x in range(N + 1)]
	for i in range(M):
		(a, b) = input().split()
		(a, b) = (int(a), int(b))
		adjacency_list[a].append(b)
		adjacency_list[b].append(a)
	levels = []
	start = int(input())
	levels.append([start])
	discovered = set()
	discovered.add(start)
	level = 1
	while levels[level - 1]:
		next_level = []
		for j in levels[level - 1]:
			for node in adjacency_list[j]:
				if node not in discovered:
					next_level.append(node)
					discovered.add(node)
		levels.append(next_level)
		level += 1
	dict_levels = {}
	for i in range(len(levels)):
		for j in levels[i]:
			dict_levels[j] = i
	output_list = []
	for i in range(1, N + 1):
		if i != start and i in dict_levels:
			print(dict_levels[i] * 6, end=' ')
		elif i != start:
			print(-1, end=' ')
	print()


tree = []

def cost(s):
	queue = []
	distance = []
	path = []
	v = 0
	w = 0
	queue.append(s - 1)
	for i in range(0, N):
		distance.append(-1)
		path.append(-1)
	distance[s - 1] = 0
	while len(queue) != 0:
		v = queue.pop(0)
		for w in range(len(tree[v])):
			if distance[w] == -1 and tree[v][w] == 1:
				distance[w] = distance[v] + 6
				path[w] = v
				queue.append(w)
	return distance
T = int(input())
for i in range(0, T):
	(N, M) = map(int, input().split(' '))
	tree = [[0 for x in range(N)] for x in range(N)]
	for i in range(0, M):
		(x, y) = map(int, input().split(' '))
		tree[x - 1][y - 1] = 1
		tree[y - 1][x - 1] = 1
	S = int(input())
	L = cost(S)
	for i in range(0, N):
		if L[i] != 0:
			print(L[i], end=' ')
	print()


import sys

def bfsshortreach(adj, s):
	dist = [sys.maxsize] * len(adj)
	dist[s - 1] = 0
	unvisited = [x for x in range(1, len(adj) + 1)]
	q = [s]
	while len(q) != 0:
		curr_node = q.pop(0)
		unvisited.remove(curr_node)
		for neighbor in adj[curr_node]:
			if neighbor in unvisited:
				if neighbor not in q:
					q.append(neighbor)
				test_distance = dist[curr_node - 1] + 6
				if test_distance < dist[neighbor - 1]:
					dist[neighbor - 1] = test_distance
	dist = [-1 if x == sys.maxsize else x for x in dist]
	return dist
num_cases = int(input())
for i in range(num_cases):
	(nodes, edges) = tuple([int(x) for x in input().split()])
	adj = {}
	for node in range(1, nodes + 1):
		adj[node] = set()
	for edge in range(edges):
		(n1, n2) = tuple([int(x) for x in input().split()])
		adj[n1].add(n2)
		adj[n2].add(n1)
	start = int(input())
	dist = bfsshortreach(adj, start)
	print(' '.join([str(x) for x in dist[:start - 1] + dist[start:]]))


def algo(graph, start, n):
	result = [-1] * (n + 1)
	result[start] = 0
	current = start
	j = -1
	v = 1
	current_list = []
	while v:
		try:
			for i in graph[current]:
				if result[i] == -1:
					result[i] = result[int(current)] + 6
					current_list.append(i)
					graph[i].remove(current)
		except:
			pass
		j += 1
		try:
			current = current_list[j]
		except IndexError:
			v = 0
	del result[start]
	del result[0]
	for j in result:
		print(j, end=' ')
	print()

def main():
	t = int(input())
	while t:
		nm = input()
		nm = nm.split()
		n = int(nm[0])
		m = int(nm[1])
		graph = {}
		i = 1
		while m:
			xy = input().split()
			x = int(xy[0])
			y = int(xy[1])
			if not x in graph:
				graph[x] = [y]
			elif not y in graph[x]:
				graph[x].append(y)
			if not y in graph:
				graph[y] = [x]
			elif not x in graph[y]:
				graph[y].append(x)
			m -= 1
		s = int(input())
		res = algo(graph, s, n)
		t -= 1
main()


from collections import defaultdict
import heapq
EDGE_WEIGHT = 6

def parse_case():
	(nv, ne) = list(map(int, input().split()))
	edges = list()
	for e in range(ne):
		edges.append(list(map(int, input().split())))
	return (Graph(nv, edges), int(input()))

class Graph:

	def __init__(self, n, edges):
		self.n = n
		neighbours = defaultdict(set)
		for (x, y) in edges:
			neighbours[x].add(y)
			neighbours[y].add(x)
		self.neighbours = neighbours

	def get_neighbours(self, x):
		return self.neighbours[x]

	def get_n(self):
		return self.n

def short_dists(g, s):
	dists = defaultdict(lambda : -1)
	dists[s] = 0
	visited = set()
	tovisit = []
	heapq.heappush(tovisit, (dists[s], s))
	while tovisit:
		(_, v) = heapq.heappop(tovisit)
		distv = dists[v]
		if v in visited:
			continue
		for n in g.get_neighbours(v):
			if dists[n] == -1 or distv + EDGE_WEIGHT < dists[n]:
				dists[n] = distv + EDGE_WEIGHT
			heapq.heappush(tovisit, (dists[n], n))
		visited.add(v)
	return dists
T = int(input())
for t in range(T):
	(g, s) = parse_case()
	dists = short_dists(g, s)
	print(' '.join(list((str(dists[v]) for v in range(1, g.get_n() + 1) if v != s))))


def create_graph(n):
	return {i: {} for i in range(1, n + 1)}

def add_directed_edge(G, x, y, weight):
	if not x in G:
		G[x] = {}
	G[x][y] = weight

def add_edge(G, x, y):
	add_directed_edge(G, x, y, 6)
	add_directed_edge(G, y, x, 6)
	return G

def breadth_first_search_tree(G, s):
	visited = []
	frontier = [(s, s, 0)]
	tree = {}
	while len(frontier) > 0:
		f = frontier.pop(0)
		if not f[0] in visited:
			visited.append(f[0])
			tree[f[0]] = (f[1], f[2])
			for q in G[f[0]]:
				if not q in visited:
					frontier.append((q, f[0], tree[f[0]][1] + G[q][f[0]]))
	return tree
T = int(input())
for t in range(T):
	[N, M] = [int(n) for n in input().split(' ')]
	G = create_graph(N)
	for m in range(M):
		[x, y] = [int(n) for n in input().split(' ')]
		add_edge(G, x, y)
	S = int(input())
	tree = breadth_first_search_tree(G, S)
	out_str = ''
	for n in range(1, N + 1):
		if n != S:
			if n in tree:
				out_str += str(tree[n][1])
			else:
				out_str += '-1'
			if n != N:
				out_str += ' '
	print(out_str)


T = int(input())

def BFS(G, S, N):
	Q = []
	pi = [-1 for k in range(N + 1)]
	col = [0 for k in range(N + 1)]
	pi[S] = 0
	col[S] = 1
	Q.append(S)
	while len(Q) > 0:
		x = Q.pop(0)
		col[x] += 1
		for e in range(1, len(G[x])):
			if G[x][e] and col[e] == 0:
				Q.append(e)
				col[e] += 1
				pi[e] = pi[x] + 6
	print((pi[1:S] + pi[S + 1:]).__str__().replace('[', '').replace(']', '').replace(',', ''))
for u in range(T):
	(N, M) = map(int, input().split())
	G = [[0 for x in range(N + 1)] for x in range(N + 1)]
	for m in range(M):
		(x, y) = map(int, input().split())
		G[x][y] = G[y][x] = 6
	S = int(input())
	BFS(G, S, N)


from collections import defaultdict, deque
n_cases = int(input())
for _ in range(n_cases):
	(n_nodes, n_edges) = (int(s) for s in input().split())
	graph = {node: set() for node in range(1, n_nodes + 1)}
	for _ in range(n_edges):
		(a, b) = (int(s) for s in input().split())
		graph[a].add(b)
		graph[b].add(a)
	start = int(input())
	hops = {node: -1 for node in graph}
	q = deque()
	visited = set()
	hops[start] = 0
	q.append(start)
	while q:
		current = q.popleft()
		visited.add(current)
		for neighbor in graph[current]:
			if neighbor in visited:
				continue
			old_hops = hops[neighbor]
			new_hops = hops[current] + 1
			if old_hops == -1 or new_hops < old_hops:
				hops[neighbor] = new_hops
			q.append(neighbor)
	paths = [hop for (node, hop) in hops.items() if node != start]
	print(' '.join((str(n) for n in map(lambda x: x if x == -1 else x * 6, paths))))


cases = int(input())

def run():
	(N, M) = list(map(int, input().split()))
	nodes = [n for n in range(1, N + 1)]
	edges = {n: set() for n in nodes}
	for i in range(M):
		(s, t) = list(map(int, input().split()))
		edges[s].add(t)
		edges[t].add(s)
	start = int(input())
	distances = {n: -1 for n in nodes}
	visited = set()
	queue = [[start, 0]]
	while queue:
		(node, distance) = queue.pop()
		if node in visited:
			continue
		distances[node] = distance
		visited.add(node)
		next_neighbors = [node for node in edges[node]]
		queue = [[n, distance + 6] for n in next_neighbors] + queue
	return ' '.join(map(str, [distances[n] for n in nodes if n != start]))
for i in range(cases):
	print(run())


DIST_EDGE = 6

class vertex:

	def __init__(self):
		self.key = 0
		self.color = None
		self.parent = None
		self.distance = float('inf')

def BFS(G, s):
	frontier = []
	vtx_list = [0] * len(G.keys())
	for key in G:
		new_vtx = vertex()
		new_vtx.color = 1
		new_vtx.key = key
		vtx_list[key] = new_vtx
	vtx_list[s].color = 0
	vtx_list[s].distance = 0
	frontier.append(s)
	while frontier:
		u = frontier.pop(0)
		for idx in G[u]:
			if vtx_list[idx].color == 1:
				vtx_list[idx].color = 0
				vtx_list[idx].distance = vtx_list[u].distance + DIST_EDGE
				vtx_list[idx].parent = vtx_list[u]
				frontier.append(idx)
		vtx_list[u].color = 2
	return vtx_list

def shortest_path(s, v, n):
	if s.key == v.key:
		return str(n)
	elif v.parent == None:
		return str(-1)
	else:
		return shortest_path(s, v.parent, n + DIST_EDGE)

def main():
	n = int(input())
	for i in range(0, n):
		myin = input().split()
		num_vtx = int(myin[0])
		num_edg = int(myin[1])
		G = {}
		for i in range(0, num_vtx):
			G[i] = []
		for i in range(0, num_edg):
			myin2 = [int(x) - 1 for x in input().split()]
			G[myin2[0]].append(myin2[1])
			G[myin2[1]].append(myin2[0])
		s = int(input()) - 1
		vtx_list = BFS(G, s)
		outlist = []
		for (i, vertex) in enumerate(vtx_list):
			if i != s:
				temp = shortest_path(vtx_list[s], vertex, 0)
				outlist.append(str(temp))
		print(' '.join(outlist))
main()


from collections import defaultdict, deque

def breadth_first_search(S, N, G, L=1):
	E = defaultdict(int)
	C = {}
	for n in range(1, N + 1):
		C[n] = -1
	E[S] += 1
	C[S] = 0
	Q = deque([S])
	while Q:
		n = Q.popleft()
		for h in G[n]:
			if E[h] == 0:
				E[h] += 1
				C[h] = C[n] + L
				Q.append(h)
	return C

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		G = defaultdict(set)
		for _ in range(M):
			E = [int(i) for i in input().split()]
			G[E[0]].add(E[1])
			G[E[1]].add(E[0])
		S = int(input())
		D = breadth_first_search(S, N, G, 6)
		print(' '.join((str(D[n]) for n in range(1, N + 1) if n != S)))
main()


import queue
tcs = int(input())
for _ in range(tcs):
	graph = {}
	scores = {}
	(nodes, edges) = map(int, input().split(' '))
	for _ in range(edges):
		(v1, v2) = map(int, input().split(' '))
		if v1 not in graph:
			graph[v1] = []
		graph[v1].append(v2)
		if v2 not in graph:
			graph[v2] = []
		graph[v2].append(v1)
	start = int(input())
	q = queue.Queue()
	q.put((start, 0))
	while not q.empty():
		(vertex, score) = q.get()
		if vertex in scores:
			continue
		scores[vertex] = score
		if vertex in graph:
			for child in graph[vertex]:
				q.put((child, score + 6))
	for i in range(1, nodes + 1):
		if i in scores:
			if scores[i]:
				print('{} '.format(scores[i]), end='')
		else:
			print('{} '.format(-1), end='')
	print()


ncases = int(input())
weight = 6
for iteration in range(ncases):
	(nnodes, nedges) = input().split()
	adj = {}
	for node in range(1, int(nnodes) + 1):
		adj[node] = []
	for nn in range(int(nedges)):
		(left, right) = map(int, input().split())
		adj[left].append(right)
		adj[right].append(left)
	start = int(input())
	queue = [start]
	visited = [start]
	length = {start: 0}
	while queue != []:
		current = queue.pop(0)
		neighbors = adj[current]
		for n in neighbors:
			if n not in visited:
				queue.append(n)
				visited.append(n)
			if n in length:
				length[n] = min(length[current] + weight, length[n])
			else:
				length[n] = length[current] + weight
	for i in [x for x in range(1, int(nnodes))]:
		if i != start:
			if i in length:
				print(length[i], end=' ')
			else:
				print(-1, end=' ')
	if int(nnodes) != start:
		if int(nnodes) in length:
			print(length[int(nnodes)])
		else:
			print(-1)


from collections import deque

class Graph:

	def __init__(self):
		self.children = []
		self.distance = -1

def BFS(G, S):
	for i in range(1, len(G)):
		G[i].distance = -1
	G[S].distance = 0
	Q = deque([S])
	while len(Q) != 0:
		u = Q.popleft()
		for i in G[u].children:
			if G[i].distance == -1:
				Q.append(i)
				G[i].distance = G[u].distance + 6
T = int(input())
for t in range(0, T):
	G = [0]
	(N, M) = [int(x) for x in input().split()]
	for i in range(1, N + 1):
		G.append(Graph())
	for i in range(0, M):
		(a, b) = [int(x) for x in input().split()]
		G[a].children.append(b)
		G[b].children.append(a)
	S = int(input())
	BFS(G, S)
	for i in range(1, N + 1):
		if i != S:
			print(G[i].distance, end=' ')
	print('')


from collections import defaultdict
from collections import deque

def BFS(graph, n, m, edge_len, sdist, start_node):
	visited = set([start_node])
	queue = deque([(start_node, 1)])
	while len(queue) != 0:
		(node, depth) = queue.popleft()
		for neighbor in graph.get(node, []):
			if neighbor not in visited:
				sdist[neighbor - 1] = depth * edge_len
				visited.add(neighbor)
				queue.append((neighbor, depth + 1))
t = int(input())
for i in range(t):
	graph = defaultdict(set)
	(n, m) = [int(x) for x in input().split()]
	for j in range(m):
		(snode, enode) = [int(x) for x in input().split()]
		graph[snode].add(enode)
		graph[enode].add(snode)
	start_node = int(input())
	sdist = [-1] * n
	edge_len = 6
	BFS(graph, n, m, edge_len, sdist, start_node)
	print(' '.join([str(d) for (k, d) in enumerate(sdist) if k != start_node - 1]))


t = int(input())
for i in range(t):
	l1 = list(map(int, input().split()))
	n = l1[0]
	m = l1[1]
	matrix = [[] for i in range(n)]
	for j in range(m):
		l2 = list(map(int, input().split()))
		matrix[l2[0] - 1].append(l2[1])
		matrix[l2[1] - 1].append(l2[0])
	state = [0 for i in range(n)]
	distance = [0 for i in range(n)]
	s = int(input())
	array = [s]
	state[s - 1] = 1
	while len(array) != 0:
		for k in matrix[array[0] - 1]:
			if state[k - 1] == 0:
				distance[k - 1] = distance[array[0] - 1] + 6
				state[k - 1] = 1
				array.append(k)
		array.pop(0)
	for j in range(n):
		if j != s - 1:
			if distance[j] == 0:
				print(-1, end=' ')
			else:
				print(distance[j], end=' ')
	print()


def toStr(x):
	if x == float('inf'):
		return str(-1)
	return str(x)
total = int(input())
for x in range(total):
	(n, m) = map(lambda x: int(x), input().split())
	nodes = list(range(1, n + 1))
	nodesDict = {}
	for u in nodes:
		nodesDict[u] = {'distance': float('inf'), 'edges': set([])}
	for e in range(m):
		(e1, e2) = tuple(map(lambda x: int(x), input().split()))
		nodesDict[e1]['edges'].add(e2)
		nodesDict[e2]['edges'].add(e1)
	s = int(input())
	nodesDict[s]['distance'] = 0
	nodes.remove(s)
	history = set([s])
	q = list(nodesDict[s]['edges'])
	while len(q) != 0:
		v = q.pop(0)
		if v not in history:
			nodesDict[v]['distance'] = min([nodesDict[w]['distance'] for w in nodesDict[v]['edges']]) + 6
			history.add(v)
			q.extend(nodesDict[v]['edges'].copy())
	print(str.join(' ', [toStr(nodesDict[i]['distance']) for i in nodes]))


from collections import defaultdict
from collections import deque

def make_adj_list(edges):
	graph = defaultdict(set)
	for (s, e) in edges:
		graph[s].add(e)
		graph[e].add(s)
	return graph

def calc_distances(graph, s, num_nodes):
	seen = set((s,))
	q = deque([[s, 0]])
	distances = [-1 for _ in range(num_nodes)]
	while q:
		(node, dist) = q.pop()
		distances[node] = dist
		for adj in graph[node]:
			if adj not in seen:
				seen.add(adj)
				q.appendleft([adj, dist + 6])
	del distances[s]
	return distances
i = int(input())
for _ in range(i):
	(n, m) = [int(el) for el in input().split()]
	edges = []
	for _ in range(m):
		(s, e) = [int(el) for el in input().split()]
		edges.append((s - 1, e - 1))
	start = int(input())
	graph = make_adj_list(edges)
	distances = calc_distances(graph, start - 1, n)
	print(' '.join((str(el) for el in distances)))


__author__ = 'akshat'
import copy

class graph:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		for i in range(1, nodes + 1):
			self.nodes[i] = set()
		self.edge_count = edges

	def add_edge(self, node1, node2, length=6):
		self.nodes[node1].add(node2)
		self.nodes[node2].add(node1)
		self.edges[node1, node2] = length
		self.edges[node2, node1] = length

	def __str__(self):
		return str(self.nodes)

	def bfs(self, start):
		(visited, queue) = (set(), [start])
		g = copy.deepcopy(self.nodes)
		path_length = [-1 for i in range(len(self.nodes) + 1)]
		path_length[start] = 0
		while queue:
			vertex = queue.pop(0)
			if vertex not in visited:
				visited.add(vertex)
				added = g[vertex] - visited
				for i in added:
					if path_length[i] == -1:
						path_length[i] = path_length[vertex] + self.edges[i, vertex]
					else:
						path_length[i] = min(path_length[i], path_length[vertex] + self.edges[i, vertex])
				queue.extend(g[vertex] - visited)
		return path_length[1:]
test_cases = int(input())
for _ in range(test_cases):
	(nodes, edges) = map(int, input().split())
	g = graph(nodes, edges)
	for _ in range(edges):
		(node1, node2) = map(int, input().split())
		g.add_edge(node1, node2)
	start = int(input())
	lst = g.bfs(start)
	lst.pop(start - 1)
	print(' '.join(map(str, lst)))


w = 6

def bfsearch(graph, toSearch, answers):
	if len(toSearch) > 0:
		node = toSearch.pop(0)
		for i in graph[node]:
			if not i in answers:
				answers[i] = answers[node] + w
				toSearch.append(i)
		bfsearch(graph, toSearch, answers)
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	graph = {}
	for j in range(1, N + 1):
		graph[j] = []
	for j in range(M):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	s = int(input())
	answers = {}
	answers[s] = 0
	toSearch = []
	for j in graph[s]:
		answers[j] = w
		toSearch.append(j)
	bfsearch(graph, toSearch, answers)
	output = ''
	for j in range(1, N + 1):
		if j != s:
			if j in answers:
				output += str(answers[j]) + ' '
			else:
				output += '-1 '
	print(output.strip())


t = int(input())
for _ in range(t):
	(n, e) = input().split()
	adj = []
	for i in range(0, int(n) + 1):
		adj.append([])
	for i in range(int(e)):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	s = int(input())
	l = [-1] * (int(n) + 1)
	l[0] = 0
	l[s] = 0
	visited = [s]
	queue = [s]
	while queue != []:
		x = queue.pop()
		for y in adj[x]:
			if l[y] == -1 or l[y] > l[x] + 6:
				l[y] = l[x] + 6
				visited.append(y)
				queue.append(y)
	for i in range(len(l)):
		if l[i] != 0:
			if i != len(l) - 1:
				print(l[i], end=' ')
			else:
				print(l[i])


from collections import deque

def BFS(edges, S):
	N = len(edges)
	nodes = [-1] * N
	nodes[S] = 0
	q = deque()
	q.append(S)
	while q:
		u = q.popleft()
		for i in range(N):
			if edges[u][i] and i != u and (nodes[i] == -1):
				nodes[i] = 6 + nodes[u]
				q.append(i)
	del nodes[S]
	print(' '.join((str(x) for x in nodes)))
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	edges = [[False] * N for _ in range(N)]
	for _ in range(M):
		(x, y) = (int(x) - 1 for x in input().split())
		edges[x][y] = edges[y][x] = True
	S = int(input()) - 1
	BFS(edges, S)


from collections import defaultdict

def print_seq(seq):
	print(' '.join(('{}'.format(v) for v in seq)))

def component(graph, start):
	(visited, queue) = (set(), [start])
	while queue:
		vertex = queue.pop(0)
		if vertex not in visited:
			visited.add(vertex)
			queue.extend(graph[vertex] - visited)
	return visited

def bfs(graph, start, goal):
	queue = [(start, [start])]
	while queue:
		(node, path) = queue.pop(0)
		for adj in graph[node] - set(path):
			if adj == goal:
				return path + [adj]
			else:
				queue.append((adj, path + [adj]))
	return []
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	graph = defaultdict(set)
	for _ in range(M):
		(x, y) = [int(x) for x in input().split()]
		graph[x].add(y)
		graph[y].add(x)
	S = int(input())
	nodes_to_reach = list(range(1, N + 1))
	nodes_to_reach.remove(S)
	component_set = component(graph, S)
	res = []
	for n in nodes_to_reach:
		if not graph[S]:
			res.append(-1)
		elif not graph[n]:
			res.append(-1)
		elif n in component_set:
			path = list(bfs(graph, S, n))
			if not path:
				res.append(-1)
			else:
				res.append((len(path) - 1) * 6)
		else:
			res.append(-1)
	print_seq(res)


def shortest_reach(g, S):
	length = 6
	sp = {}
	for k in g:
		sp[k] = -1
	sp[S] = 0
	queue = []
	queue.append([S, g[S]])
	while queue:
		current_nodes = queue.pop(0)
		for current_node in current_nodes[1]:
			if sp[current_node] == -1:
				sp[current_node] = sp[current_nodes[0]] + length
				queue.append([current_node, g[current_node]])
	return sp

def print_sp(sp, S):
	for key in sorted(sp):
		if key != S:
			print(sp[key], end=' ')
T = int(input())
shortest_paths = []
for case in range(T):
	g = {}
	N = [int(x) for x in input().split()][0]
	for i in range(N):
		g[i] = []
	while True:
		pair = [int(x) for x in input().split()]
		if len(pair) == 2:
			g[pair[0] - 1].append(pair[1] - 1)
			g[pair[1] - 1].append(pair[0] - 1)
		else:
			S = pair[0] - 1
			break
	shortest_paths.append([S, shortest_reach(g, S)])
for shortest_path in shortest_paths:
	print_sp(shortest_path[1], shortest_path[0])
	print()


nooftestcases = int(input())
for i in range(nooftestcases):
	(noofvertices, noofedges) = [int(x) for x in input().split(' ')]
	graph = {}
	for i in range(noofvertices):
		graph[i + 1] = [[], 0, 'white']
	for i in range(noofedges):
		(vertex1, vertex2) = [int(x) for x in input().split(' ')]
		graph[vertex1][0].append(vertex2)
		graph[vertex2][0].append(vertex1)
	startingpos = int(input())
	currentpos = startingpos
	queue = [currentpos]
	while queue != []:
		currentpos = queue.pop(0)
		for vertex in graph[currentpos][0]:
			if graph[vertex][2] == 'white':
				queue.append(vertex)
				graph[vertex][2] = 'gray'
				graph[vertex][1] = graph[currentpos][1] + 6
		graph[currentpos][2] = 'black'
	for vertex in range(1, noofvertices + 1):
		if vertex != startingpos:
			if graph[vertex][1] == 0:
				print(-1, end=' ')
			else:
				print(graph[vertex][1], end=' ')
	print()


import queue
trials = int(input())

class Graph:

	def __init__(self, numNodes, numEdges):
		self.numNodes = numNodes
		self.numEdges = numEdges
		self.node = {}

	def addNode(self, node):
		n = Node(node)
		self.node[node] = n

	def addUEdge(self, node1, node2):
		self.node[node1].addEdge(self.node[node2])
		self.node[node2].addEdge(self.node[node1])

	def BFS(self, node):
		for key in range(1, len(self.node) + 1):
			self.node[key].reset()
		self.node[node].color = 1
		self.node[node].distance = 0
		queue = []
		queue.append(node)
		while len(queue) > 0:
			u = queue[0]
			queue = queue[1:]
			for adjNode in self.node[u].adj:
				if self.node[adjNode].distance == -1:
					self.node[adjNode].distance = self.node[u].distance + 1
					queue.append(adjNode)
		out = []
		for key in self.node:
			d = self.node[key].distance
			if d != 0:
				if d == -1:
					out.append(-1)
				else:
					out.append(d * 6)
		output = ''
		for i in range(0, len(out)):
			output += str(out[i])
			if i < len(out) - 1:
				output += ' '
		print(output)

class Node:

	def __init__(self, name):
		self.adj = []
		self.color = 0
		self.name = name
		self.distance = -1

	def addEdge(self, node):
		self.adj.append(node.name)

	def reset(self):
		self.color = 0
		self.distance = -1
while trials > 0:
	trials -= 1
	(nodes, edges) = map(int, input().split(' '))
	G = Graph(nodes, edges)
	for i in range(0, nodes):
		G.addNode(i + 1)
	for i in range(0, edges):
		(x, y) = map(int, input().split(' '))
		G.addUEdge(x, y)
	G.BFS(int(input()))


import collections

class node:

	def __init__(self, uid):
		self.uid = uid
		self.neighbors = []
		self.distance = 0
cases = int(input())
for i in range(0, cases):
	nodes = {}
	l1 = list(map(int, input().split()))
	num_nodes = l1[0]
	num_edges = l1[1]
	l2 = []
	for j in range(0, num_nodes):
		n = node(j)
		nodes[j] = n
	for j in range(0, num_edges):
		l2.append(list(map(int, input().split())))
		v1 = l2[j][0] - 1
		v2 = l2[j][1] - 1
		n1 = node(v1)
		n2 = node(v2)
		if n1.uid not in nodes:
			nodes[n1.uid] = n1
			if v2 not in nodes[n1.uid].neighbors:
				nodes[n1.uid].neighbors.append(v2)
		else:
			nodes[n1.uid].neighbors.append(v2)
		if n2.uid not in nodes:
			nodes[n2.uid] = n2
			if v1 not in nodes[n2.uid].neighbors:
				nodes[n2.uid].neighbors.append(v1)
		else:
			nodes[n2.uid].neighbors.append(v1)
	start = int(input()) - 1
	pos = start
	d = collections.deque()
	d.append(pos)
	visited = []
	visited.append(pos)
	s = ''
	p = 0
	while len(d) > 0:
		pos = d.popleft()
		for k in nodes[pos].neighbors:
			if k not in visited and nodes[k].distance == 0:
				d.append(k)
				visited.append(k)
				nodes[k].distance = nodes[pos].distance + 6
	visited = []
	for k in nodes.values():
		if k.uid != start:
			if nodes[k.uid].distance == 0:
				s += '-1 '
			else:
				s += str(nodes[k.uid].distance) + ' '
		p += 1
	while p < num_nodes:
		s += '-1 '
		p += 1
	print(s)


from collections import defaultdict

class UndirectedGraph:

	def __init__(self):
		self.nodes = set()
		self.edges = {}
		self.adj = defaultdict(set)
		return

	def addNode(self, x):
		self.nodes.add(x)
		return

	def addEdge(self, x, y, dist):
		self.edges[x, y] = dist
		self.edges[y, x] = dist
		self.adj[x].add(y)
		self.adj[y].add(x)
		return

def BFS(s, adj):
	level = {s: 0}
	parent = {s: None}
	i = 1
	frontier = [s]
	while frontier:
		nextFrontier = list()
		for u in frontier:
			for v in sorted(adj[u]):
				if v not in level:
					level[v] = i
					parent[v] = u
					nextFrontier.append(v)
		frontier = nextFrontier
		i += 1
	return (level, parent)

def runBFS():
	(N, M) = map(int, input().strip().split())
	Graph = UndirectedGraph()
	for i in range(1, N + 1):
		Graph.addNode(i)
	for _ in range(M):
		(X, Y) = map(int, input().strip().split())
		dist = 6
		Graph.addEdge(X, Y, 6)
	source = int(input().strip())
	(level, parent) = BFS(source, Graph.adj)
	for i in range(1, N + 1):
		if i == source:
			continue
		try:
			print(6 * level[i], end=' ')
		except KeyError:
			print(-1, end=' ')
	print()
TC = int(input())
for _ in range(TC):
	runBFS()


L = int(input())
for j in range(0, L):
	inp = input().split(' ')
	count = 0
	ver = {}
	visited = []
	N = int(inp[1])
	ans = []
	for i in range(0, int(inp[0])):
		ans.append(-1)
	for i in range(0, N):
		edge = input().split(' ')
		try:
			ver[edge[0]].append(edge[1])
		except KeyError:
			temp = [edge[1]]
			ver[edge[0]] = temp
		try:
			ver[edge[1]].append(edge[0])
		except KeyError:
			temp = [edge[0]]
			ver[edge[1]] = temp
	start = input()
	queue = [start]
	temp = []
	visited.append(start)
	try:
		while queue:
			for i in queue:
				ans[int(i) - 1] = count * 6
				for k in ver[i]:
					if not k in visited:
						temp.append(k)
						visited.append(k)
			queue = temp
			temp = []
			count += 1
		ans[int(start) - 1] = -2
	except KeyError:
		ans[int(start) - 1] = -2
	for i in ans:
		if i != -2:
			print(i, end=' ')
	print('')


def main():
	test = int(input())
	while test > 0:
		shortestbfs()
		test -= 1

def shortestbfs():
	(n, m) = list(map(int, input().split()))
	graph = [[0 for i in range(n)] for x in range(n)]
	for i in range(m):
		(x, y) = list(map(lambda x: int(x) - 1, input().split()))
		graph[x][y] = graph[y][x] = 1
	start = int(input()) - 1
	bfs(graph, n, start)

def bfs(graph, n, start):
	visited = [False for i in range(n)]
	visited[start] = True
	queue = [start]
	path = [-1 for i in range(n)]
	path[start] = 0
	while queue != []:
		v = queue.pop(0)
		for i in [adj for (adj, e) in enumerate(graph[v]) if e == 1]:
			if visited[i]:
				continue
			visited[i] = True
			queue += [i]
			path[i] = path[v] + 6
	print(' '.join(map(str, [x for (i, x) in enumerate(path) if i != start])))
main()


from collections import deque

def DFS(G, S):
	queue = deque('')
	S = S - 1
	G[S][S] = 0
	queue.append(S)
	while len(queue) > 0:
		vertex = queue.popleft()
		for i in range(len(G)):
			if G[vertex][i] == 1:
				if G[i][i] == -1:
					G[i][i] = G[vertex][vertex] + 6
					queue.append(i)
	for i in range(len(G)):
		if G[i][i] != 0:
			print(G[i][i], end=' ')
T = int(input())
for i in range(T):
	inp = list(map(int, input().split()))
	N = inp[0]
	M = inp[1]
	graph = [[-1 for j in range(N)] for e in range(N)]
	for j in range(M):
		inp = list(map(int, input().split()))
		graph[inp[0] - 1][inp[1] - 1] = 1
		graph[inp[1] - 1][inp[0] - 1] = 1
	S = int(input())
	DFS(graph, S)
	print('')


from collections import deque

def find_shortest(g, s):
	expansion = deque([(s, 0)])
	expanded = dict()
	while len(expansion) > 0:
		(node, path_length) = expansion.popleft()
		if node in expanded:
			continue
		expanded[node] = path_length
		for j in g[node]:
			if j not in expanded:
				expansion.append((j, path_length + 6))
	return (expanded[i] if i in expanded else -1 for i in range(1, len(g) + 1) if i != s)
for k in range(int(input())):
	(nodes, edges) = (int(x) for x in input().split())
	graph = {i: [] for i in range(1, nodes + 1)}
	for n in range(edges):
		(i, j) = (int(x) for x in input().split())
		graph[i].append(j)
		graph[j].append(i)
	start = int(input())
	print(*find_shortest(graph, start))


from heapq import *

def test_graph(l, g, s):
	dist = [-1] * l
	(q, seen) = ([(0, s)], set())
	while q:
		(cost, v1) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			dist[v1] = cost
			for x in g[v1]:
				if x not in seen:
					heappush(q, (cost + 6, x))
	print(' '.join([str(dist[x]) for x in range(l) if x != s]))
t = int(input())
for x in range(t):
	(V, E) = map(int, input().split())
	graph = [[] for i in range(V)]
	for y in range(E):
		(n1, n2) = map(int, input().split())
		graph[n1 - 1].append(n2 - 1)
		graph[n2 - 1].append(n1 - 1)
	s = int(input())
	test_graph(V, graph, s - 1)


import collections

class Graph:

	def __init__(self, N, M, edges):
		self.N = N
		self.M = M
		self.edges = [set() for i in range(N)]
		for e in edges:
			self.addEdge(e)

	def addEdge(self, e):
		(p1, p2) = e
		p1 -= 1
		p2 -= 1
		self.edges[p1].add(p2)
		self.edges[p2].add(p1)

	def calcShortestTo(self, p):
		dist = [-1 for i in range(self.N)]
		dist[p] = 0
		q = collections.deque()
		q.append(p)
		while q:
			n = q.popleft()
			for m in self.edges[n]:
				if dist[m] == -1:
					dist[m] = dist[n] + 1
					q.append(m)
		return dist
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	edges = [map(int, input().split()) for i in range(M)]
	g = Graph(N, M, edges)
	dist = g.calcShortestTo(int(input()) - 1)
	s = ''
	for d in dist:
		if d > 0:
			s += str(d * 6) + ' '
		if d == -1:
			s += '-1 '
	print(s)


from collections import OrderedDict
from collections import defaultdict
import asyncio

class Graph:

	def __init__(self):
		self.neighbors = defaultdict(set)
		self.vertices = list()

	def add_edge(self, start, end):
		self.neighbors[start].add(end)
		self.neighbors[end].add(start)

def dijkstra(graph, start):
	infinity = object()
	distances = OrderedDict()
	for vertex in graph.vertices:
		distances[vertex] = infinity
	distances[start] = 0
	trampoline = list()

	def compute(current):
		for neighbor in graph.neighbors[current]:
			new = distances[current] + 6
			if distances[neighbor] is infinity or distances[neighbor] > new:
				distances[neighbor] = new
				trampoline.append(neighbor)
	trampoline.append(start)
	while trampoline:
		vertex = trampoline.pop(0)
		compute(vertex)
	distances = list(distances.values())
	distances.pop(start - 1)
	return map(lambda x: -1 if x is infinity else x, distances)
T = int(input())
for _ in range(T):
	graph = Graph()
	(N, M) = map(int, input().split())
	for name in range(1, N + 1):
		graph.vertices.append(name)
	for _ in range(M):
		(start, end) = map(int, input().split())
		graph.add_edge(start, end)
	S = int(input())
	print(' '.join(map(str, dijkstra(graph, S))))


for i in range(int(input())):
	(n, m) = [int(i) for i in input().split(' ')]
	nodes = [[False] * n for i in range(n)]
	for j in range(m):
		(s, e) = [int(k) - 1 for k in input().split(' ')]
		if s < e:
			nodes[s][e] = True
		else:
			nodes[e][s] = True
	_open = [int(input()) - 1]
	ans = [-1] * n
	count = 0
	next_open = []
	while True:
		while _open != []:
			cur = _open[0]
			ans[cur] = count * 6
			for j in range(n):
				if (nodes[cur][j] or nodes[j][cur]) and ans[j] == -1:
					ans[j] = -2
					next_open = next_open + [j]
			_open = _open[1:]
		if next_open == []:
			break
		else:
			count += 1
			_open = next_open
			next_open = []
	ans = filter(lambda x: x != 0, ans)
	print(' '.join([str(i) for i in ans]))


from collections import deque
T = int(input())
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	graph = {}
	for i in range(N):
		graph[i + 1] = []
	for _ in range(M):
		(a, b) = [int(i) for i in input().split()]
		graph[a].append(b)
		graph[b].append(a)
	explored = [-1] * (N + 1)
	s = int(input())
	explored[s] = 0
	queue = deque([s])
	while queue:
		s = queue.popleft()
		for i in graph[s]:
			if explored[i] == -1:
				explored[i] = explored[s] + 6
				queue.append(i)
	result = ''
	for i in range(1, N + 1):
		if explored[i] != 0:
			result += str(explored[i])
			if i != N:
				result += str(' ')
	print(result)


nOR = int(input().strip())

class Vertex:

	def __init__(self):
		self.name = '-'
		self.previous = '-'
		self.distance = '-'
for a in range(nOR):
	output = ''
	vertices = []
	nAndM = input().strip().split()
	N = int(nAndM[0])
	M = int(nAndM[1])
	for n in range(N):
		vertex = Vertex()
		vertex.name = n
		vertices.append(vertex)
	adjMat = [[0 for x in range(N)] for y in range(N)]
	for m in range(M):
		edge = input().strip().split()
		adjMat[int(edge[0]) - 1][int(edge[1]) - 1] = 1
		adjMat[int(edge[1]) - 1][int(edge[0]) - 1] = 1
	startVertex = int(input().strip()) - 1
	if not 1 in adjMat[startVertex]:
		for n in range(N - 1):
			output += '-1 '
	else:
		queue = [vertices[startVertex]]
		while not len(queue) == 0:
			currentVertex = queue.pop(0)
			currentLocation = currentVertex.name
			if 1 in adjMat[currentLocation]:
				for i in range(N):
					if adjMat[currentLocation][i] == 1 and (not i == startVertex):
						if vertices[i].previous == '-':
							vertices[i].previous = currentLocation
							vertices[i].distance = 1
							queue.append(vertices[i])
		for n in range(N):
			if not n == startVertex:
				distance = 1
				if vertices[n].previous == '-':
					output += '-1 '
				else:
					while not vertices[n].previous == '-' and (not int(vertices[n].previous) == startVertex):
						if vertices[n].previous == '-':
							output += '-1 '
						else:
							distance += 1
							n = int(vertices[n].previous)
					output += str(distance * 6) + ' '
	print(output)


T = int(input())
t = 0
while t < T:
	(N, M) = [int(x) for x in input().split()]
	from collections import defaultdict
	adjL = defaultdict(list)
	for i in range(1, N + 1):
		adjL[i].append(i)
		adjL[i].remove(i)
	for i in range(0, M):
		(x, y) = [int(x) for x in input().split()]
		adjL[x].append(y)
		adjL[y].append(x)
	s = int(input())
	visited = {}
	weights = {}

	def bfs(s, adj):
		for i in range(1, len(adj) + 1):
			visited[i] = False
			weights[i] = float('inf')
		from collections import deque
		itr = 0
		q = deque(maxlen=len(adj))
		visited[s] = True
		weights[s] = itr
		q.append(s)
		while len(q) > 0:
			x = q.popleft()
			for y in adj[x]:
				if not visited[y]:
					visited[y] = True
					weights[y] = weights[x] + 1
					q.append(y)
				else:
					continue
	bfs(s, adjL)
	weights = list(weights.values())
	weights.remove(0)
	for i in range(0, len(weights)):
		weights[i] = weights[i] * 6
	toprint = ''
	for i in weights:
		if i > 0:
			if i != float('inf'):
				toprint += str(i) + ' '
			else:
				toprint += '-1 '
	toprint.strip()
	print(toprint)
	t += 1


from collections import deque
t = int(input())
while t:
	(n, m) = map(int, input().split())
	graph = {x: [] for x in range(1, n + 1)}
	pathCost = [-1 for x in range(n)]
	while m:
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
		m -= 1
	source = int(input())
	list1 = deque()
	list1.append(source)
	pathCost[source - 1] = 0
	visited = [source]
	while list1:
		item = list1.popleft()
		for dest in graph[item]:
			if dest not in visited:
				pathCost[dest - 1] = pathCost[item - 1] + 6
				visited.append(dest)
				list1.append(dest)
	string1 = ''
	for x in range(n):
		if x != source - 1:
			string1 += str(pathCost[x]) + ' '
	print(string1)
	t -= 1


import sys

def bfs(g, s):
	distance = {}
	for v in g:
		distance[v] = sys.maxsize
	distance[s] = 0
	q = {s: distance[s]}
	while q:
		u = min(q.items(), key=lambda x: x[1])[0]
		del q[u]
		for v in g[u]:
			if distance[v] > distance[u] + 6:
				distance[v] = distance[u] + 6
				q[v] = distance[v]
	result = []
	for x in range(1, N + 1):
		if x != s and x in distance:
			if distance[x] < sys.maxsize:
				result.append(distance[x])
			else:
				result.append(-1)
	return result
T = int(input())
for i in range(T):
	graph = {}
	(N, M) = [int(x) for x in input().split()]
	for x in range(1, N + 1):
		graph[x] = []
	for _ in range(M):
		(x, y) = [int(x) for x in input().split()]
		graph[x].append(y)
		graph[y].append(x)
	S = int(input())
	print(' '.join((str(x) for x in bfs(graph, S))))


class Node:

	def __init__(self, num):
		self.label = num
		self.edges = []
		self.distance = 99999999

class Edge:

	def __init__(self, a, b, num):
		self.left = a
		self.right = b
		a.edges.append(self)
		b.edges.append(self)
		self.label = num
cases = [{} for i in range(0, int(input()))]
for case in cases:
	(case['N'], case['M']) = [int(n) for n in input().split()]
	case['nodes'] = [Node(n) for n in range(0, case['N'])]
	case['edges'] = []
	for m in range(0, case['M']):
		(a, b) = [int(i) - 1 for i in input().split()]
		ed = Edge(case['nodes'][a], case['nodes'][b], m)
		case['edges'].append(ed)
	case['start'] = int(input()) - 1
	start = case['start']
	N = case['N']
	M = case['M']
	nodes = case['nodes']
	edges = case['edges']
	stack = []
	first = nodes[start]
	first.distance = 0
	stack.insert(0, first)
	while len(stack) > 0:
		current = stack.pop()
		dist = current.distance
		for edge in current.edges:
			if not edge.left == current:
				nextnode = edge.left
			elif not edge.right == current:
				nextnode = edge.right
			else:
				nextnode = False
			if not nextnode == False:
				if nextnode.distance > dist + 6:
					nextnode.distance = dist + 6
					stack.insert(0, nextnode)
	answer = ''
	for node in nodes:
		if not node == first:
			if node.distance == 99999999:
				answer += '-1 '
			else:
				answer += str(node.distance) + ' '
	print(answer)


T = int(input())

def foo():
	ne = input().split()
	(N, E) = (int(ne[0]), int(ne[1]))
	nodes = [[] for i in range(N)]
	visited = [0 for i in range(N)]
	dists = [-1 for i in range(N)]
	for i in range(E):
		edge = input().split()
		(e1, e2) = (int(edge[0]), int(edge[1]))
		nodes[e1 - 1].append(e2 - 1)
		nodes[e2 - 1].append(e1 - 1)
	S = int(input())
	Q = [S - 1]
	dists[S - 1] = 0
	while len(Q) > 0:
		node = Q[0]
		visited[node] = 1
		for n in nodes[node]:
			if visited[n] == 1:
				continue
			visited[n] = 1
			dists[n] = dists[node] + 6
			Q.append(n)
		del Q[0]
	del dists[S - 1]
	output = ' '.join((str(d) for d in dists))
	print(output)
for t in range(T):
	foo()


class node:

	def __init__(self, id):
		self.id = id
		self.connections = []
		self.distance = -1

def BFS(S, nodes, edge_length):
	nodes[S - 1].distance = 0
	Q = [S]
	while len(Q) > 0:
		u = Q.pop()
		for n in nodes[u - 1].connections:
			if nodes[n - 1].distance == -1:
				nodes[n - 1].distance = nodes[u - 1].distance + edge_length
				Q.insert(0, n)
	print_this = ''
	for n in nodes:
		if n.distance != 0:
			print_this = print_this + str(n.distance) + ' '
	print(print_this)
cases = int(input())
for c in range(0, cases):
	info = input().split()
	info = list(map(int, info))
	N = info[0]
	E = info[1]
	nodes = []
	for n in range(1, N + 1):
		nodes.append(node(n))
	for e in range(0, E):
		edge = input().split()
		edge = list(map(int, edge))
		nodes[edge[0] - 1].connections.append(edge[1])
		nodes[edge[1] - 1].connections.append(edge[0])
	S = int(input())
	BFS(S, nodes, 6)


from queue import Queue

def readEdges(edgeNum):
	edges = []
	for _ in range(edgeNum):
		(node1, node2) = [int(node) for node in input().split()]
		edges.append((node1, node2))
	return edges

def buildGraph(edges):
	graph = {}
	for (node1, node2) in edges:
		addUndirectedEdge(graph, node1, node2)
	return graph

def addUndirectedEdge(graph, node1, node2):
	addDirectedEdge(graph, node1, node2)
	addDirectedEdge(graph, node2, node1)

def addDirectedEdge(graph, fromNode, toNode):
	if fromNode in graph:
		graph[fromNode].add(toNode)
	else:
		graph[fromNode] = set([toNode])

def findShortestPath(graph, nodeNum, startNode):
	size = nodeNum + 1
	shortestPath = [-1] * size
	queue = Queue()
	shortestPath[startNode] = 0
	queue.put(startNode)
	while not queue.empty():
		fromNode = queue.get()
		toNodeArr = graph.get(fromNode)
		if toNodeArr is not None:
			for toNode in toNodeArr:
				if shortestPath[toNode] == -1:
					shortestPath[toNode] = shortestPath[fromNode] + 6
					queue.put(toNode)
	del shortestPath[startNode]
	return shortestPath[1:]

def printShortestPath(shortestPath):
	print(' '.join(map(str, shortestPath)))
n = int(input())
for _ in range(n):
	(nodeNum, edgeNum) = [int(num) for num in input().split()]
	edges = readEdges(edgeNum)
	startNode = int(input())
	graph = buildGraph(edges)
	shortestPath = findShortestPath(graph, nodeNum, startNode)
	printShortestPath(shortestPath)


import queue

def bfs(graph, s, v, path):
	q = queue.Queue()
	q.put(s)
	v[s] = 1
	while q.empty() == False:
		j = q.get()
		for i in graph[j]:
			if v[i] == 0:
				v[i] = 1
				path[i] = path[j] + 6
				q.put(i)

def main():
	for i in range(int(input())):
		(n, e) = input().split()
		(n, e) = (int(n), int(e))
		graph = []
		for k in range(n):
			graph.append([])
		for j in range(e):
			(a, b) = input().split()
			(a, b) = (int(a), int(b))
			graph[a - 1].append(b - 1)
			graph[b - 1].append(a - 1)
		s = int(input())
		v = [0] * n
		path = [0] * n
		bfs(graph, s - 1, v, path)
		o = ''
		for x in range(len(path)):
			if x == s - 1:
				continue
			if path[x] == 0:
				o += str(-1) + ' '
			else:
				o += str(path[x]) + ' '
		print(o)
main()


T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	graph = {}
	for i in range(1, N + 1):
		graph[str(i)] = []
	for m in range(M):
		(a, b) = input().split()
		graph[a].append(b)
		graph[b].append(a)
	S = input()
	to_visit = list(zip(graph[S], [6] * len(graph[S])))
	visited = {S: 0}
	while to_visit != []:
		node = to_visit.pop()
		if node[0] in visited:
			continue
		else:
			visited[node[0]] = node[1]
			to_visit[:0] = zip(graph[node[0]], [node[1] + 6] * len(graph[node[0]]))
	for i in range(1, N + 1):
		node = str(i)
		if node == S:
			continue
		elif node in visited:
			print(visited[node], end=' ' if i != N else '\n')
		else:
			print(-1, end=' ' if i != N else '\n')


class Node:

	def __init__(self, _id):
		self.id = _id
		self.connections = []
		self.distance = -1
		self.visited = False

	def __repr__(self):
		return str(self.id)

	def __str__(self):
		return str(self.id)

	def __eq__(self, other):
		return self.id == other.id

	def __hash__(self):
		return hash(self.id)

	def add_connection(self, node):
		if node not in self.connections:
			self.connections.append(node)

	def next_nodes(self):
		return [x for x in self.connections if not x.visited]

class Graph:

	def __init__(self):
		self.nodes = []

	def add_node(self, _id):
		self.nodes.append(Node(_id))

	def add_vertex(self, vertex):
		start = vertex[0]
		end = vertex[1]
		self.nodes[start - 1].add_connection(self.nodes[end - 1])
		self.nodes[end - 1].add_connection(self.nodes[start - 1])
tests = int(input())
for _ in range(tests):
	line2 = input().split()
	n = int(line2[0])
	m = int(line2[1])
	vertices = []
	for _ in range(m):
		vertices.append(tuple((int(x) for x in input().split())))
	vertices = list(set(vertices))
	s = int(input())
	graph = Graph()
	for i in range(1, n + 1):
		graph.add_node(i)
	for i in range(len(vertices)):
		graph.add_vertex(vertices[i])
	current = [graph.nodes[s - 1]]
	current[0].visited = True
	depth = 0
	run = True
	while run:
		new = set()
		depth += 1
		for cur in current:
			conn = cur.next_nodes()
			for node in conn:
				node.visited = True
				node.distance = 6 * depth
				new.add(node)
		current = new
		if not new:
			run = False
	for x in range(len(graph.nodes)):
		if x + 1 != s:
			print(graph.nodes[x].distance, end=' ')
	print()


from collections import deque
t = int(input())
for case in range(t):
	(n, m) = [int(x) for x in input().split()]
	nodes = [set() for x in range(n)]
	for line in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		if b not in nodes[a]:
			nodes[a].add(b)
		if a not in nodes[b]:
			nodes[b].add(a)
	s = int(input()) - 1
	dist = {x: -1 for x in range(n)}
	q = deque()
	q.append((s, 0))
	visited = set([s])
	while q:
		(node, d) = q.popleft()
		dist[node] = d
		for adj in nodes[node]:
			if dist[adj] == -1:
				q.append((adj, d + 6))
				dist[adj] = 0
	output = []
	for x in range(0, n):
		if x != s:
			output.append(str(dist[x]))
	print(' '.join(output))


def bfs_paths(graph, start, goal):
	queue = [(start, [start])]
	while queue:
		(v, path) = queue.pop(0)
		for next in graph[v] - set(path):
			if next == goal:
				yield (path + [next])
			else:
				queue.append((next, path + [next]))

def shortest_path(graph, start, goal):
	if len(graph[start]) == 0 or len(graph[goal]) == 0:
		return -1
	try:
		return 6 * (len(next(bfs_paths(graph, start, goal))) - 1)
	except StopIteration:
		return -1
t = int(input())
for tt in range(t):
	ret = []
	(n, m) = map(int, input().split())
	graph = dict(((i, set()) for i in range(1, n + 1)))
	for mm in range(m):
		(s, d) = map(int, input().split())
		graph[s].add(d)
		graph[d].add(s)
	start = int(input())
	for a in list((x for x in range(1, n + 1) if x != start)):
		ret.append(shortest_path(graph, start, a))
	print(' '.join(map(str, ret)))


class Graph(object):

	def __init__(self, N, M):
		(self.N, self.M) = (N, M)
		self.alist = {key: list() for key in range(1, N + 1)}
		for index in range(M):
			(t, h) = [int(value) for value in input().split()]
			self.alist[t].append(h)
			self.alist[h].append(t)

	def bfs(self, source):
		distances = {key: -1 for key in range(1, self.N + 1)}
		to_explore = set([source])
		current_distance = 0
		while to_explore:
			next_nodes = set()
			for tnode in to_explore:
				if distances[tnode] == -1:
					distances[tnode] = current_distance
					next_nodes.update(self.alist[tnode])
			to_explore = next_nodes
			current_distance += 1
		self.distances = distances

	def answer(self, source):
		self.bfs(source)
		for index in range(1, N + 1):
			if index == source:
				continue
			elif self.distances[index] == -1:
				print(-1, end=' ')
			else:
				print(6 * self.distances[index], end=' ')
		print()
T = int(input())
for index in range(T):
	(N, M) = [int(value) for value in input().split()]
	graph = Graph(N, M)
	source = int(input())
	graph.answer(source)