Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn't show the village roads (or side lanes) on it and shows only the main roads. 

The map of the city is a graph consisting $N$ nodes (labeled $\mbox{I}$ to $N$) where a specific given node $\mbox{S}$ represents the current position of Rust and the rest of the nodes denote other places in the city, and an edge between two nodes is a main road between two places in the city. It can be suitably assumed that an edge that doesn't exist/isn't shown on the map is a village road (side lane). That means, there is a village road between two nodes $\boldsymbol{\alpha}$ and $\boldsymbol{b}$ iff(if and only if) there is no city road between them.  

In this problem, distance is calculated as number of village roads (side lanes) between any two places in the city.

Rust wants to calculate the shortest distance from his position (Node $\mbox{S}$) to all the other places in the city if he travels only using the village roads (side lanes).

Note: The graph/map of the city is ensured to be a sparse graph.

Input Format

The first line contains $\mathbf{T}$, denoting the number of test cases. $\mathbf{T}$ testcases follow. 

First line of each test case has two integers $N$, denoting the number of cities in the map and $\mbox{M}$, denoting the number of roads in the map. 

The next $\mbox{M}$ lines each consist of two space-separated integers $\boldsymbol{x}$ and $y$ denoting a main road between city $\boldsymbol{x}$ and city $y$. 
The last line has an integer $\mbox{S}$, denoting the current position of Rust. 

Constraints

$1\leq T\leq10$  
$2\leq N\leq2\times10^5$  
$0\leq M\leq120000$  
$1\leq x,y,S\leq N$  

Note  

No nodes will have a road to itself.   
There will not be multiple edges between any pair of nodes i.e. there is at most one undirected edge between them.   
Graph is guaranteed to be sparse. 
It is guranteed that there will be a path between any pair of nodes using the side lanes.

Output Format

For each of T test cases, print a single line consisting of N-1 space separated integers, denoting the shortest distances of the remaining N-1 places from Rust's position (that is all distances, except the source node to itself) using the village roads/side lanes in ascending order based on vertex number.  

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

Sample Output 0
3 1 2
2 2 1

Explanation 0

The graph in the first testcase can be shown as:

Here the source node is 1 (marked S). 

The distance from 1 to 2 is 3. Path: 1 -> 3 -> 4 -> 2 

The distance from 1 to 3 is 1. Path: 1 -> 3 

The distance from 1 to 4 is 2. Path: 1 -> 3 -> 4

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
from collections import deque
import sys

def bfs(s, pe, res, n, pe1):
	notdiscovered = set(range(1, n + 1))
	q = deque()
	level = 0
	q.append((s, level))
	notdiscovered.discard(s)
	while q and notdiscovered:
		v = q.popleft()
		i = v[0]
		level = v[1] + 1
		nd = []
		print('lnd=', len(notdiscovered), file=sys.stderr)
		for j in notdiscovered:
			if j == i:
				continue
			if i not in pe1 and j not in pe1 or ((i, j) not in pe and (j, i) not in pe):
				q.append((j, level))
				nd.append(j)
				res[j] = level
		for j in nd:
			notdiscovered.discard(j)
	return res
t = int(input().strip())
for tc in range(t):
	nm = [int(i) for i in input().strip().split()]
	n = nm[0]
	m = nm[1]
	pe = set()
	pe1 = set()
	for r in range(m):
		nm = [int(i) for i in input().strip().split()]
		x = nm[0]
		y = nm[1]
		pe.add((x, y))
		pe1.add(x)
		pe1.add(y)
	s = int(input().strip())
	res = [None] * (n + 1)
	res = bfs(s, pe, res, n, pe1)
	out = ''
	for x in res:
		if x != None:
			if len(out):
				out += ' ' + str(x)
			else:
				out = str(x)
	print(out)


nc = int(input())
for ca in range(nc):
	(n, m) = (int(t) for t in input().split())
	edges = [(int(t) - 1 for t in input().split()) for i in range(m)]
	s = int(input()) - 1
	fanout = [set() for i in range(n)]
	for (x, y) in edges:
		fanout[x].add(y)
		fanout[y].add(x)
	layer = [-1] * n
	bdd = {s}
	fog = set(range(n)).difference(bdd)
	idx = 0
	allBlocked = [-1] * n
	while len(bdd) > 0:
		for a in bdd:
			layer[a] = idx
		nextbdd = {f for f in fog if not bdd.issubset(fanout[f])}
		fog = fog.difference(nextbdd)
		bdd = nextbdd
		idx += 1
	print(' '.join((str(t) for t in layer if t > 0)))


from queue import Queue
T = int(input())
for case in range(T):
	(N, M) = map(int, input().split())
	inv = [set() for i in range(N)]
	for i in range(M):
		(u, v) = map(int, input().split())
		inv[u - 1].add(v - 1)
		inv[v - 1].add(u - 1)
	S = int(input()) - 1
	undiscovered = [u for u in inv[S]]
	dist = [1 for i in range(N)]
	dist[S] = 0
	for v in undiscovered:
		dist[v] = None
	q = Queue()
	for v in range(N):
		if dist[v] == 1:
			q.put(v)
	while not q.empty():
		u = q.get()
		i = 0
		while i < len(undiscovered):
			if undiscovered[i] not in inv[u]:
				dist[undiscovered[i]] = dist[u] + 1
				q.put(undiscovered[i])
				del undiscovered[i]
			else:
				i += 1
	del dist[S]
	print(' '.join(map(str, dist)))


def add_edge(x, y):
	try:
		adj[x][y] = 1
	except KeyError:
		adj[x] = {y: 1}

def is_done(ind):
	for x in prev:
		if x not in adj[ind] and x not in rem:
			return True
	return False
t = int(input())
for i in range(0, t):
	(n, m) = list(map(int, input().split()))
	adj = dict()
	for j in range(0, m):
		(x, y) = list(map(int, input().split()))
		add_edge(x, y)
		add_edge(y, x)
	s = int(input())
	ans = [1] * (n + 1)
	ans[s] = 0
	if s in adj:
		rem = adj[s].copy()
	else:
		rem = dict()
	prev = dict(((x, 1) for x in range(1, n + 1) if x not in rem))
	while rem.__len__() > 0:
		new_rem = dict()
		for val in rem.keys():
			ans[val] += 1
			if not is_done(val):
				new_rem[val] = 1
		prev = dict(((x, 1) for x in rem if x not in new_rem))
		rem = new_rem
	for i in range(1, n + 1):
		if i != s:
			print(ans[i], end=' ')
	print()


from queue import Queue

def BFS(v, n):
	q = Queue()
	L1 = [x for x in range(1, n + 1)]
	L1.remove(v)
	L2 = []
	q.put(v)
	D[v] = 0
	while not q.empty():
		u = q.get()
		color[u] = 2
		L2 = []
		for x in G[u]:
			if color[x] == 0:
				L1.remove(x)
				L2.append(x)
		for x in L1:
			q.put(x)
			D[x] = D[u] + 1
			color[x] = 1
		L1 = L2
G = []
D = []
color = []
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	G = [[] for x in range(n + 1)]
	D = [0 for x in range(n + 1)]
	color = [0 for x in range(n + 1)]
	for _ in range(m):
		(x, y) = list(map(int, input().split()))
		G[x].append(y)
		G[y].append(x)
	s = int(input())
	BFS(s, n)
	for x in range(1, n + 1):
		if x != s:
			print(D[x], end=' ')
	print()


class Graph(object):

	def __init__(self, city_count):
		self.city_count = city_count
		self.cities = range(city_count)
		self.roads = [set() for c in self.cities]

	def add_road(self, frm, to):
		frm -= 1
		to -= 1
		self.roads[frm].add(to)
		self.roads[to].add(frm)

	def calculate_shortest_from(self, start):
		start -= 1
		distances = [None] * self.city_count
		unknown = set(self.cities)
		unknown.remove(start)
		to_consider = [start]
		distance = 0
		while to_consider and unknown:
			next_level = set()
			distance += 1
			for s in to_consider:
				if not unknown:
					break
				reachable = self.roads[s]
				for dst in list(unknown):
					if s == dst:
						continue
					if dst not in reachable:
						distances[dst] = distance
						unknown.remove(dst)
						next_level.add(dst)
			to_consider = next_level
		return distances
for t in range(int(input())):
	(city_count, road_count) = [int(t) for t in input().split()]
	g = Graph(city_count)
	for m in range(road_count):
		(frm, to) = [int(t) for t in input().split()]
		g.add_road(frm, to)
	start = int(input())
	for d in g.calculate_shortest_from(start):
		if d is not None:
			print(d, end=' ')
	print()


def range_with_exclude(start: int, stop: int, exclude: list):
	i = start
	exclude_pos = 0
	while True:
		excl_len = len(exclude)
		while exclude_pos < excl_len and exclude[exclude_pos] == i and (i < stop):
			i += 1
			exclude_pos += 1
		if i >= stop:
			break
		yield i
		i += 1

def solve(N, E, s):
	EL = [[] * N for _ in range(N)]
	for e in E:
		EL[e[0]].append(e[1])
		EL[e[1]].append(e[0])
	V = [False] * N
	D = [float('inf')] * N
	D[s] = 0
	V[s] = True
	Q = set([s])
	while len(Q) > 0 and sum((1 for v in V if v)) < N:
		if sum((1 for v in V if not v)) < 0.01 * N:
			not_visited_nodes_visited_neighbors = set()
			not_visited_nodes = [i for i in range(N) if not V[i]]
			for i in not_visited_nodes:
				for n in range_with_exclude(0, N, EL[i]):
					if V[n]:
						not_visited_nodes_visited_neighbors.add(n)
			selectable_nodes = Q.intersection(not_visited_nodes_visited_neighbors)
		else:
			selectable_nodes = Q
		a = min(selectable_nodes, key=lambda e: D[e])
		Q.remove(a)
		x = y = 0
		for e in range_with_exclude(0, N, EL[a]):
			y += 1
			if V[e]:
				continue
			x += 1
			new_dis = D[a] + 1
			if new_dis < D[e]:
				D[e] = new_dis
				V[e] = True
				Q.add(e)
	del D[s]
	print(' '.join(map(str, D)))

def main():
	T = int(input())
	for t in range(T):
		(n, m) = map(int, input().split())
		e = []
		for _ in range(m):
			(x, y) = map(int, input().split())
			e.append((x - 1, y - 1))
		s = int(input())
		solve(n, e, s - 1)
main()


from collections import deque
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	paths = set()
	for j in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		paths.add((min(a, b), max(a, b)))
	s = int(input()) - 1
	distances = [-1 for x in range(n)]
	notVisited = [x for x in range(n)]
	q = deque([s])
	distances[s] = 0
	dist = 0
	count = 1
	nxt = 0
	while q:
		city = q.popleft()
		distances[city] = dist
		notVisitedNew = []
		for to in notVisited:
			if (min(city, to), max(city, to)) not in paths:
				q.append(to)
				nxt += 1
			else:
				notVisitedNew.append(to)
		notVisited = notVisitedNew
		count -= 1
		if count == 0:
			count = nxt
			nxt = 0
			dist += 1
	print(*distances[:s] + distances[s + 1:], sep=' ')


T = int(input())

def bfs(graph, start, citiesLen):
	queue = [(start, 0)]
	notvisited = set((x for x in range(1, citiesLen + 1)))
	cities = ['0' for x in range(citiesLen + 1)]
	i = 0
	c = 1
	while i < len(queue):
		(vertex, depth) = queue[i]
		notvisited.discard(vertex)
		visited = set()
		for next in notvisited:
			if cities[next] == '0' and next not in graph[vertex]:
				cities[next] = str(depth + 1)
				visited.add(next)
				c += 1
				queue.append((next, depth + 1))
		notvisited = notvisited - visited
		i += 1
		if c == citiesLen + 1:
			break
	return cities[1:start] + cities[start + 1:]
for case in range(T):
	(cities, roads) = [int(x) for x in input().split()]
	graph = [0]
	for c in range(1, cities + 1):
		graph.append(set())
	for r in range(roads):
		(x, y) = map(int, input().split())
		graph[x].add(y)
		graph[y].add(x)
	start = int(input())
	res = []
	print(' '.join(bfs(graph, start, cities)))


__author__ = 'ncompane'
__author__ = 'ncompane'
from operator import itemgetter
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)}
	distances = {x: 0 for x in range(1, n + 1)}
	for j in range(m):
		(v1, v2) = input().split()
		(v1, v2) = (int(v1), int(v2))
		edges[v1].append(v2)
		edges[v2].append(v1)
	s = int(input())
	visited = 1
	unvisited = {x for x in range(1, n + 1)}
	unvisited.remove(s)
	BFS_q = [s]
	while visited < n:
		current = BFS_q.pop(0)
		current_dist = distances[current] + 1
		nodes_not_to_visit = set()
		for neighbour in edges[current]:
			if neighbour in unvisited:
				nodes_not_to_visit.add(neighbour)
		for node in nodes_not_to_visit:
			unvisited.remove(node)
		for node in unvisited:
			distances[node] = current_dist
			BFS_q.append(node)
			visited += 1
		unvisited = nodes_not_to_visit
	dist_list = distances.items()
	dist_list = sorted(dist_list, key=itemgetter(0))
	for x in dist_list:
		if x[0] != s:
			print(x[1], end=' ')
	print()


import heapq

def dijkstra(graph, start):
	visited = set()
	distances = dict()
	all_nodes = set(graph.keys())
	heap = []
	for key in graph:
		if key == start:
			continue
		distances[key] = 2147483648
	distances[start] = 0
	heapq.heappush(heap, (0, start))
	visited.add(start)
	weight = 1
	while len(heap) > 0 and len(visited) != len(all_nodes):
		(_, vertex) = heapq.heappop(heap)
		for neighbour in all_nodes:
			if neighbour in graph[vertex] or neighbour in visited:
				continue
			new_distance = distances[vertex] + weight
			if new_distance < distances[neighbour]:
				distances[neighbour] = new_distance
				heapq.heappush(heap, (new_distance, neighbour))
				visited.add(neighbour)
	return distances
test_cases = int(input())
for test_case in range(test_cases):
	(n, m) = [int(i) for i in input().strip().split()]
	graph = {}
	for i in range(1, n + 1):
		graph[i] = set()
	for i in range(0, m):
		(s, e) = [int(j) for j in input().strip().split()]
		graph[s].add(e)
		graph[e].add(s)
	start = int(input())
	distances = dijkstra(graph, start)
	dst = []
	for i in range(1, n + 1):
		if i == start:
			continue
		if distances[i] == 2147483648:
			dst.append(str(-1))
		else:
			dst.append(str(distances[i]))
	print(' '.join(dst))


tests = int(input())
for _ in range(tests):
	(n, m) = map(int, input().split())
	g = {}
	to_visit = set()
	for i in range(1, n + 1):
		g[i] = set()
		to_visit.add(i)
	for i in range(m):
		(s, e) = map(int, input().split())
		g[s].add(e)
		g[e].add(s)
	start = int(input())
	visited = {}
	stack = [start]
	to_visit.remove(start)
	distance = 0
	while stack:
		distance += 1
		tmp = []
		for u in stack:
			adj = set()
			for v in g[u]:
				if v in to_visit:
					adj.add(v)
					to_visit.remove(v)
			for e in to_visit:
				tmp.append(e)
				visited[e] = distance
			to_visit = adj
		stack = tmp
	print(' '.join(map(str, [visited[v] for v in range(1, n + 1) if v != start])))


from itertools import product
from collections import defaultdict, deque

def SidewayDistance(Start, v, CityRoad, N):
	if v not in CityRoad[Start]:
		return 1
	if len(CityRoad[Start].union(CityRoad[v])) < N:
		return 2
	allSet = set([i for i in range(N)])
	curDepth = 1
	vFree = allSet.difference(CityRoad[v])
	vFree.remove(v)
	newlyAdded = set([i for i in vFree])
	while Start not in vFree:
		curDepth += 1
		vFreeBefore = set([i for i in vFree])
		for nv in newlyAdded:
			nvFree = allSet.difference(CityRoad[nv])
			nvFree.remove(nv)
			vFree = vFree.union(nvFree)
		if Start in vFree:
			return curDepth
		else:
			newlyAdded = vFree.difference(vFreeBefore)
T = int(input())
for _ in range(T):
	(N, M) = tuple(map(int, input().split()))
	CityRoad = defaultdict(set)
	for e in range(M):
		(v1, v2) = tuple(map(lambda x: int(x) - 1, input().split()))
		CityRoad[v1].add(v2)
		CityRoad[v2].add(v1)
	Start = int(input()) - 1
	Distance = [0] * N
	for v in range(N):
		if v != Start:
			print(SidewayDistance(Start, v, CityRoad, N), end=' ')
	print()


import sys

def d(*args):
	pass
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	dist = [-1 for __ in range(n)]
	adj = [set() for __ in range(n)]
	for __ in range(m):
		(i, j) = map(int, input().split())
		i -= 1
		j -= 1
		adj[i].add(j)
		adj[j].add(i)
	s = int(input())
	s -= 1
	last = {s}
	remaining = set(range(n))
	di = 1
	while remaining:
		l = len(last)
		d('Remaining:', remaining, 'rank', di, ':', last)
		cur = set()
		next = set()
		for i in remaining:
			if len(adj[i].intersection(last)) == l:
				d(i, 'has a main road from each node in the last rank')
				next.add(i)
			else:
				d(i, 'has a side path from one of the nodes in the last rank')
				cur.add(i)
				d('Distance of', i, ':', di)
				dist[i] = di
		last = cur
		di += 1
		remaining = next
	print(' '.join((str(v) for (k, v) in enumerate(dist) if k != s)))


def heappush(heap, token):
	index = len(heap)
	heap.append(token)
	while index > 0 and token[1] < heap[(index - 1) // 2][1]:
		(heap[index], heap[(index - 1) // 2]) = (heap[(index - 1) // 2], heap[index])
		index = (index - 1) // 2

def heappop(heap):
	value = heap[0]
	if len(heap) == 1:
		return heap.pop(0)
	heap[0] = heap.pop(-1)
	index = 0
	while 2 * index + 1 < len(heap):
		if 2 * index + 2 < len(heap) and heap[index][1] > min(heap[2 * index + 1][1], heap[2 * index + 2][1]):
			offset = 1 if heap[2 * index + 1][1] < heap[2 * index + 2][1] else 2
			(heap[index], heap[2 * index + offset]) = (heap[2 * index + offset], heap[index])
			index = 2 * index + offset
		elif 2 * index + 2 == len(heap) and heap[index][1] > heap[2 * index + 1][1]:
			(heap[index], heap[2 * index + 1]) = (heap[2 * index + 1], heap[index])
		else:
			break
	return value

def contains(list, val):
	for element in list:
		if val == element:
			return True
	return False
t = int(input().strip())
for _ in range(t):
	(v, e) = input().strip().split(' ')
	(v, e) = [int(v), int(e)]
	adj_list = [{} for _ in range(v)]
	for _ in range(e):
		(s, d) = input().strip().split(' ')
		(s, d) = [int(s) - 1, int(d) - 1]
		adj_list[s][d] = True
		adj_list[d][s] = True
	start = int(input().strip()) - 1
	shortest_dist = [-1] * v
	shortest_dist[start] = 0
	queue = [(start, 0)]
	updates = 1
	while queue != []:
		(node, steps) = queue.pop(0)
		for dest in range(v):
			if dest not in adj_list[node]:
				if shortest_dist[dest] == -1:
					shortest_dist[dest] = steps + 1
					updates += 1
					if updates >= v:
						break
					queue.append((dest, steps + 1))
		if updates >= v:
			break
	shortest_dist.pop(start)
	print(' '.join([str(temp) for temp in shortest_dist]))


from collections import *

def hunt(N, edges, s):
	dists = [0] * (N + 1)
	Q = deque([])
	Q.append(s)
	nv = set([x for x in range(1, N + 1) if x != s])
	to_rem = set()
	while len(Q) > 0:
		c = Q.popleft()
		for x in nv:
			if (x, c) not in edges:
				to_rem.add(x)
				dists[x] = dists[c] + 1
				Q.append(x)
		nv = nv - to_rem
		to_rem = set()
	return [str(dists[x]) for x in range(1, N + 1) if x != s]
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().strip().split())
	edges = set()
	for _ in range(M):
		(a, b) = map(int, input().strip().split())
		edges.add((a, b))
		edges.add((b, a))
	s = int(input())
	print(' '.join(hunt(N, edges, s)))


from collections import deque

def resol(nodes, s):
	n = len(nodes)
	tots = set(range(n))
	pendents = deque([s])
	fets = set([s])
	dist = [0 for x in range(n)]
	d = 1
	while pendents and len(fets) < n:
		nous = False
		p = pendents.pop()
		for x in tots - (set(nodes[p]) | fets):
			nous += 1
			fets.add(x)
			dist[x] = d
			pendents.append(x)
		if nous:
			d += 1
	return ' '.join([str(dist[x]) for x in range(n) if x != s])

def main():
	t = int(input())
	for tt in range(t):
		(n, m) = [int(x) for x in input().split()]
		nodes = [deque() for x in range(n)]
		for mm in range(m):
			(a, b) = [int(x) - 1 for x in input().split()]
			nodes[a].append(b)
			nodes[b].append(a)
		s = int(input()) - 1
		print(resol(nodes, s))
main()


from queue import Queue
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	neighbors = []
	for _ in range(n):
		neighbors.append(set())
	for _ in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		neighbors[a].add(b)
		neighbors[b].add(a)
	s = int(input()) - 1
	distances = [-1] * n
	unvisited = set(range(n))
	distances[s] = 0
	unvisited.remove(s)
	q = Queue()
	q.put(s)
	while not q.empty():
		cur = q.get()
		visited = set()
		for i in unvisited:
			if i not in neighbors[cur]:
				q.put(i)
				distances[i] = distances[cur] + 1
				visited.add(i)
		unvisited -= visited
		if len(unvisited) == 0:
			break
	print(' '.join([str(x) for x in distances if x != 0]))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


from collections import defaultdict
from queue import PriorityQueue

def ucs(graph, start):
	queue = PriorityQueue()
	for i in unvisited:
		queue.put((1, i))
	vertex_set = set(range(1, n + 1))
	while not queue.empty():
		(length, vertex) = queue.get()
		if ans[vertex] < length:
			continue
		neighbours = vertex_set - graph[vertex]
		temp = length + 1
		for v in neighbours:
			if ans[v] == -1:
				ans[v] = temp
				queue.put((ans[v], v))
			elif ans[v] > temp:
				ans[v] = temp
				queue.put((ans[v], v))
t = int(input())
for _ in range(t):
	(n, e) = (int(i) for i in input().split())
	graph = defaultdict(set)
	ans = [1] * (n + 1)
	for _ in range(e):
		(i, j) = (int(i) for i in input().split())
		graph[i].add(j)
		graph[j].add(i)
	start = int(input())
	ans[start] = 0
	for i in graph[start]:
		ans[i] = -1
	visited = set(range(1, n + 1)) - graph[start]
	source = set(visited)
	unvisited = set(graph[start])
	step = 2
	flag = True
	while flag:
		flag = False
		next_source = set()
		for node in source:
			for next_node in unvisited - graph[node]:
				if next_node in unvisited:
					flag = True
					unvisited.discard(next_node)
					ans[next_node] = step
					next_source.add(next_node)
		step += 1
		source = set(next_source)
	ans.pop(start)
	ans.pop(0)
	print(*ans)


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input().strip())
for _ in range(tests):
	(num_locations, num_main_roads) = [int(x) for x in input().split()]
	distances = [1] * num_locations
	locations = {}
	for _ in range(num_main_roads):
		(location_a, location_b) = [int(id) for id in input().split()]
		if location_a not in locations:
			locations[location_a] = set()
		if location_b not in locations:
			locations[location_b] = set()
		locations[location_a].add(location_b)
		locations[location_b].add(location_a)
	root = int(input().strip())
	unvisited = locations.get(root, set())
	visited = set()
	dist = 2
	while len(unvisited):
		for location in unvisited:
			if len(unvisited | locations[location]) < num_locations:
				distances[location - 1] = dist
				visited.add(location)
		unvisited = unvisited - visited
		visited = set()
		dist += 1
	del distances[root - 1]
	print(' '.join([str(distance) for distance in distances]))


from collections import *

def track(N, citymap, s):
	dists = [0] * N
	n = range(N)
	nodes = set(n)
	trace = set([s])
	Q = deque([s])
	dist = 1
	while len(Q) > 0 and len(trace) < N:
		i = False
		point = Q.pop()
		for x in nodes - (set(citymap[point]) | trace):
			i += 1
			trace.add(x)
			dists[x] = dist
			Q.append(x)
		if i:
			dist += 1
	return [str(dists[x]) for x in n if x != s]
T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	citymap = [deque() for x in range(N)]
	for edge in range(M):
		(a, b) = [int(x) - 1 for x in input().split()]
		citymap[a].append(b)
		citymap[b].append(a)
	S = int(input()) - 1
	print(' '.join(track(N, citymap, S)))


from collections import deque
from heapq import heappush, heappop

def read_graph(n, m):
	global lines
	g = {}
	for i in range(m):
		(u, v) = [int(x) for x in input().strip().split(' ')]
		if u not in g:
			g[u] = {}
		if v not in g:
			g[v] = {}
		g[u][v] = True
		g[v][u] = True
	return g

def find_distances(g, s, n):
	dist = {s: 0}
	q = []
	heappush(q, [0, s])
	visited = {}
	nodes = set([x for x in range(1, n + 1)])
	while len(q) > 0:
		(curr_dist, u) = heappop(q)
		visited[u] = True
		x = nodes - set(g[u].keys())
		x.remove(u)
		for v in x:
			c = curr_dist + 1
			if v not in visited:
				if v in dist:
					if c < dist[v]:
						heappush(q, [c, v])
						dist[v] = c
				else:
					heappush(q, [c, v])
					dist[v] = c
	return dist
T = int(input().strip())
for t in range(T):
	(n, m) = [int(x) for x in input().strip().split(' ')]
	g = read_graph(n, m)
	s = int(input().strip())
	rc = []
	if s not in g:
		rc = [1 for x in range(n - 1)]
	elif len(g) == n:
		sp = find_distances(g, s, n)
		for val in range(1, n + 1):
			if s != val:
				rc.append(sp[val])
	else:
		for val in range(1, n + 1):
			if s != val:
				if val not in g or val not in g[s]:
					rc.append(1)
				else:
					rc.append(2)
	print(*rc)


from copy import deepcopy
T = int(input())
for testCase in range(T):
	(N, M) = input().split(' ')
	N = int(N)
	M = int(M)
	E = [set() for i in range(N)]
	for i in range(M):
		(a, b) = input().split(' ')
		a = int(a) - 1
		b = int(b) - 1
		E[a].add(b)
		E[b].add(a)
	S = int(input()) - 1
	pathLengths = [0 for i in range(N)]
	pathCount = 1
	queue = [S]
	while pathCount < N and len(queue) > 0:
		curr = queue[0]
		queue = queue[1:]
		neighbors = set(range(N))
		for cityRoad in E[curr]:
			neighbors.discard(cityRoad)
		for adj in neighbors:
			if adj != S and (not pathLengths[adj]):
				pathLengths[adj] = pathLengths[curr] + 1
				pathCount += 1
				queue.append(adj)
	print(' '.join((str(length) for length in pathLengths if length != 0)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


x = int(input())
for n in range(x):
	(C, R) = map(int, input().split())
	roadlist = []
	distlist = []
	for i in range(C):
		roadlist.append(set())
		distlist.append(1)
	for i in range(R):
		(a, b) = map(int, input().split())
		roadlist[a - 1].add(b)
		roadlist[b - 1].add(a)
	start = int(input())
	nvisit = roadlist[start - 1]
	while len(nvisit) > 0:
		h = set()
		for i in nvisit:
			if len(nvisit | roadlist[i - 1]) < C:
				h.add(i)
			distlist[i - 1] += 1
		nvisit = nvisit - h
	del distlist[start - 1]
	output = ' '.join((str(i) for i in distlist))
	print(output)


case_count = int(input())
for case in range(case_count):
	(a, b) = input().split()
	city_count = int(a)
	main_road_count = int(b)
	main_road = {}
	for city in range(city_count + 1):
		main_road[city] = set()
	for road in range(main_road_count):
		(c, d) = input().split()
		departure = int(c)
		destination = int(d)
		main_road[departure].add(destination)
		main_road[destination].add(departure)
	derective_location = int(input())
	unvisited_city = set((i for i in range(1, city_count + 1)))
	distance = [-1 for _ in range(city_count + 1)]
	distance[derective_location] = 0
	bfs_q = [derective_location]
	while len(bfs_q) > 0 and len(unvisited_city) > 0:
		front = bfs_q[0]
		bfs_q = bfs_q[1:]
		available = set(unvisited_city)
		available = available - main_road[front]
		for city in available:
			if distance[city] == -1:
				bfs_q.append(city)
				distance[city] = distance[front] + 1
		unvisited_city = unvisited_city - available
	del distance[derective_location]
	del distance[0]
	print(' '.join((str(i) for i in distance)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


for test in range(int(input())):
	(cities, roads) = (int(i) for i in input().split())
	distances = [1] * cities
	roads_dict = {}
	for road in range(roads):
		(a, b) = (int(i) for i in input().split())
		if a not in roads_dict:
			roads_dict[a] = set()
		if b not in roads_dict:
			roads_dict[b] = set()
		roads_dict[a].add(b)
		roads_dict[b].add(a)
	root_node = int(input())
	if root_node in roads_dict:
		unvisited = roads_dict[root_node]
	else:
		unvisited = set()
	curr_visited = set()
	curr_dist = 2
	while len(unvisited) > 0:
		for n in unvisited:
			union = unvisited | roads_dict[n]
			if len(union) < cities:
				distances[n - 1] = curr_dist
				curr_visited.add(n)
		unvisited = unvisited - curr_visited
		curr_visited = set()
		curr_dist += 1
	del distances[root_node - 1]
	result = ''
	for d in distances:
		result += str(d) + ' '
	print(result[:-1])


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import sys
from collections import defaultdict

def solve_case(n_cities, city_adj, start):
	distances = n_cities * [sys.maxsize]
	visited = set([start])
	unvisited = set(range(n_cities)) - visited
	dist = 0
	to_explore = set([start])
	while len(to_explore) != 0:
		next_adj = set(unvisited)
		for city in to_explore:
			distances[city] = dist
			next_adj.intersection_update(city_adj[city])
		visited.update(to_explore)
		unvisited.difference_update(to_explore)
		dist += 1
		to_explore = unvisited - next_adj
	print(' '.join([str(x) for x in distances[:start] + distances[start + 1:]]))
n_cases = int(input().strip())
for _ in range(n_cases):
	(n_cities, n_roads) = [int(x) for x in input().strip().split(' ')]
	city_adj = defaultdict(set)
	for _ in range(n_roads):
		(a, b) = [int(x) - 1 for x in input().strip().split(' ')]
		city_adj[a].add(b)
		city_adj[b].add(a)
	start = int(input().strip()) - 1
	solve_case(n_cities, city_adj, start)


c = int(input())
for c0 in range(c):
	(n, m) = input().strip().split(' ')
	(n, m) = (int(n), int(m))
	close = {}
	missing = {}
	done = {}
	distance = [-1] * (n + 1)
	for n0 in range(1, n + 1):
		close[n0] = []
		missing[n0] = 1
	for m0 in range(m):
		(c1, c2) = input().strip().split(' ')
		(c1, c2) = (int(c1), int(c2))
		close[c1].append(c2)
		close[c2].append(c1)
	s = int(input())
	del missing[s]
	done[s] = 1
	end = False
	cont = 1
	while not end:
		missing2 = {}
		done2 = {}
		end = True
		for cc in missing:
			d = 0
			for cl in done:
				if not cl in close[cc]:
					d = cont
					break
			if d > 0:
				distance[cc] = d
				done2[cc] = 1
			else:
				missing2[cc] = 1
				end = False
		missing = missing2
		done = done2
		cont += 1
	string = ''
	for i in range(1, n + 1):
		if i == s:
			continue
		string += '%d ' % distance[i]
	print(string)


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


class UndirectedGraph:

	def __init__(self, vertexCount):
		self.vertexCount = vertexCount
		self.edgeMap = {}
testcount = int(input().strip())
for _ in range(testcount):
	(vertexCount, edgeCount) = list(map(int, input().strip().split(' ')))
	graph = UndirectedGraph(vertexCount)
	for _ in range(edgeCount):
		(u, v) = list(map(int, input().strip().split(' ')))
		if u not in graph.edgeMap:
			graph.edgeMap[u] = set()
		if v not in graph.edgeMap:
			graph.edgeMap[v] = set()
		graph.edgeMap[u].add(v)
		graph.edgeMap[v].add(u)
	sVertex = int(input().strip())
	if sVertex not in graph.edgeMap:
		dist = [1] * (vertexCount - 1)
		print(str(dist).replace('[', '').replace(']', '').replace(',', ''))
		continue
	l1 = {}
	for iLoop in range(1, vertexCount + 1):
		if iLoop == sVertex:
			continue
		l1[iLoop] = True
	dist = {sVertex: 0}
	queue = [sVertex]
	visitedMap = {sVertex: True}
	while len(queue) > 0:
		vertex = queue.pop(0)
		l2 = {}
		if vertex in graph.edgeMap:
			for v in graph.edgeMap[vertex]:
				if v not in visitedMap:
					del l1[v]
					l2[v] = True
		for v in l1.keys():
			visitedMap[v] = True
			queue.append(v)
			dist[v] = dist[vertex] + 1
		l1 = l2
	for iLoop in range(1, vertexCount + 1):
		if iLoop == sVertex:
			continue
		print(dist[iLoop], end=' ')
	print()


from collections import defaultdict, deque
T = int(input())
for t in range(T):
	(N, M) = [int(i) for i in input().split()]
	G = defaultdict(set)
	D = [float('inf') for _ in range(N + 1)]
	nodes = set(range(1, N + 1))
	for m in range(M):
		e = [int(i) for i in input().split()]
		G[e[0]].add(e[1])
		G[e[1]].add(e[0])
	src = int(input())
	nodes.remove(src)
	queue = deque([(src, 0)])
	while queue and nodes:
		(v, d) = queue.popleft()
		d += 1
		temp = []
		for n in nodes:
			if n not in G[v]:
				temp.append(n)
				D[n] = str(d)
				queue.append((n, d))
		for t in temp:
			nodes.remove(t)
	print(' '.join([s for (i, s) in enumerate(D) if i != src][1:]))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	G = [[] for _ in range(N)]
	for _ in range(M):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		G[u].append(v)
		G[v].append(u)
	s = int(input())
	s -= 1
	c = [-1] * N
	c[s] = 0
	(d, n) = (0, 1)
	while n > 0:
		n2 = 0
		for i in range(N):
			if c[i] != -1:
				continue
			cnt = 0
			for j in G[i]:
				if c[j] == d:
					cnt += 1
			if cnt < n:
				c[i] = d + 1
				n2 += 1
		d += 1
		n = n2
	print(' '.join(map(str, c[:s] + c[s + 1:])))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


T = int(input().strip())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	graph = {}
	for _ in range(M):
		(x, y) = (int(x) - 1 for x in input().split())
		if not x in graph:
			graph[x] = set()
		if not y in graph:
			graph[y] = set()
		graph[x].add(y)
		graph[y].add(x)
	S = int(input().strip()) - 1
	res = [1] * N
	res[S] = 0
	if not S in graph:
		print(' '.join(['1'] * (N - 1)))
		continue
	unreached = graph[S]
	reached = {x for x in range(N) if x not in unreached}
	while unreached:
		newreached = set()
		for x in unreached:
			res[x] += 1
			if not reached <= graph[x]:
				newreached.add(x)
		unreached = unreached - newreached
		reached = reached | newreached
	print(' '.join((str(x) for (i, x) in enumerate(res) if i != S)))


import copy
cases = int(input())
for case in range(cases):
	(nodes, edges) = map(int, input().split())
	adjl = [[] for _ in range(nodes)]
	for _ in range(edges):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		adjl[x].append(y)
		adjl[y].append(x)
	start = int(input()) - 1
	costl = [1 for _ in range(nodes)]
	not_visited_que = adjl[start]
	cost = 2
	while not_visited_que:
		new_not_visited_que = []
		for node in not_visited_que:
			if len(set(not_visited_que) | set(adjl[node])) == nodes:
				new_not_visited_que.append(node)
			else:
				costl[node] = cost
		cost += 1
		not_visited_que = copy.deepcopy(new_not_visited_que)
	costl.pop(start)
	print(' '.join([str(item) for item in costl]))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	edges = set()
	for i in range(m):
		(x, y) = map(int, input().split())
		edges.add((x - 1, y - 1))
		edges.add((y - 1, x - 1))
	s = int(input()) - 1
	distances = [None] * n
	distances[s] = 0
	q = [s]
	p = 0
	while len(q) < n:
		for x in range(n):
			if distances[x] is None and (q[p], x) not in edges:
				distances[x] = distances[q[p]] + 1
				q.append(x)
		p += 1
	print(' '.join(map(str, filter(None, distances))))


def lstin():
	return list(map(int, input().strip().split()))

def iin():
	return int(input().strip())
for _ in range(iin()):
	(N, M) = lstin()
	edges = [set() for _ in range(N + 1)]
	for _ in range(M):
		(u, v) = lstin()
		edges[u].add(v)
		edges[v].add(u)
	S = iin()
	dists = [1] * (N + 1)
	d = 2
	nv = edges[S]
	while nv:
		visited = set()
		for u in nv:
			if len(nv | edges[u]) != N:
				dists[u] = d
				visited.add(u)
		nv -= visited
		d += 1
	for it in (range(1, S), range(S + 1, N + 1)):
		for i in it:
			print(dists[i], end=' ')
	print()


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


def BFS(u, n, adj):
	visited = [-1] * (n + 1)
	que = []
	que.append(u)
	visited[u] = 0
	while que:
		v = que.pop(0)
		for w in adj[v]:
			if visited[w] == -1:
				que.append(w)
				visited[w] = visited[v] + 1
	return visited
t = int(input().strip())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	adj = {j: set() for j in range(n + 1)}
	for _ in range(m):
		(u, v) = tuple(map(int, input().split()))
		adj[u].add(v)
		adj[v].add(u)
	s = int(input().strip())
	distances = [1] * n
	not_visited = adj[s]
	new = set()
	current = 2
	while not_visited:
		for i in not_visited:
			diff = not_visited | adj[i]
			if len(diff) < n:
				distances[i - 1] = current
				new.add(i)
		not_visited = not_visited - new
		new = set()
		current += 1
	del distances[s - 1]
	print(' '.join([str(i) for i in distances]))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


from collections import defaultdict

def get_list(type_=int):
	return [type_(x) for x in input().strip().split(' ')]

def compute(graph, N, S):
	distances = [None for _ in range(N + 1)]
	unmarked = set({i for i in range(1, N + 1)})
	unmarked.remove(S)
	wave = [S]
	distances[S] = 0
	num = 0
	while wave:
		num += 1
		iter_wave = iter(wave)
		adjacent = graph[next(iter_wave)]
		for v in iter_wave:
			adjacent = adjacent.intersection(graph[v])
			if not adjacent:
				break
		new_wave = unmarked.difference(adjacent)
		for x in new_wave:
			distances[x] = num
		unmarked = unmarked.difference(new_wave)
		wave = new_wave
	return ' '.join((str(d) for d in distances[1:S] + distances[S + 1:]))
T = get_list()[0]
for _ in range(T):
	graph = defaultdict(set)
	(N, M) = get_list()
	for _ in range(M):
		(x, y) = get_list()
		graph[x].add(y)
		graph[y].add(x)
	S = get_list()[0]
	print(compute(graph, N, S))


import queue
T = int(input())
for t in range(T):
	(n_v, n_e) = [int(i) for i in input().split()]
	n_v += 1
	c_adj = [set() for i in range(n_v)]
	dist = [float('inf')] * n_v
	discovered = queue.Queue()
	for e in range(n_e):
		(p, q) = [int(i) for i in input().split()]
		c_adj[p].add(q)
		c_adj[q].add(p)
	s = int(input())
	dist[s] = 0
	discovered.put(s)
	undiscovered = {i for i in range(1, n_v) if i != s}
	while len(undiscovered) > 0:
		g = discovered.get()
		for u in undiscovered.copy():
			if u not in c_adj[g]:
				dist[u] = dist[g] + 1
				discovered.put(u)
				undiscovered.remove(u)
	print(' '.join([str(dist[i]) for i in range(1, n_v) if i != s]))


n_cases = int(input().strip())

def bfs(graph, start, goal, rec_dict):
	if goal not in rec_dict:
		stack = [(start, 0)]
		visited = []
		while stack:
			(vertex, n) = stack.pop(0)
			if vertex == goal:
				rec_dict[goal] = n
				break
			if vertex not in visited:
				visited.append(vertex)
				for v in graph[vertex]:
					if v not in stack:
						stack.append((v, n + 1))
	return rec_dict[goal]

def find_sideroads(N_city, main_road, S):
	main_map = []
	for n in range(N_city):
		main_map.append([1] * N_city)
	for i in range(N_city):
		main_map[i][i] = 0
	for r in main_road:
		main_map[r[0] - 1][r[1] - 1] = 0
		main_map[r[1] - 1][r[0] - 1] = 0
	map_dict = dict()
	for i in range(N_city):
		map_dict[i] = [i for (i, e) in enumerate(main_map[i]) if e != 0]
	record_dict = dict()
	result = []
	for i in range(N_city):
		if i != S - 1:
			result.append(bfs(map_dict, S - 1, i, record_dict))
	print(' '.join([str(x) for x in result]))
result = []
from collections import defaultdict
for i in range(n_cases):
	(n_city, n_road) = [int(x) for x in input().strip().split(' ')]
	main_road = defaultdict(list)
	for i in range(n_road):
		(n1, n2) = [int(x) for x in input().strip().split(' ')]
		main_road[n1].append(n2)
		main_road[n2].append(n1)
	s = int(input().strip())
	nodes = list(range(1, n_city + 1))
	not_visited = set(main_road[s])
	frontier = set(nodes) - not_visited - set([s])
	dist = [1] * n_city
	dist[s - 1] = 0
	current_dist = 1
	while not_visited:
		prev = frontier
		frontier = set()
		current_dist += 1
		for n in not_visited:
			connected = False
			for v in prev:
				if n not in main_road[v]:
					connected = True
				if connected:
					dist[n - 1] = current_dist
					frontier.add(n)
					break
		not_visited = not_visited - frontier
	print(' '.join([str(x) for x in dist if x > 0]))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


from collections import deque

def bfs(n, g, start):
	dists = [None] * n
	dists[start] = 0
	num_found = 1
	queue = deque([start])
	while num_found < n and queue:
		v = queue.popleft()
		for u in range(n):
			if dists[u] is not None or v in g[u]:
				continue
			queue.append(u)
			dists[u] = dists[v] + 1
			num_found += 1
	return dists
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	neighbours = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		neighbours[u - 1].add(v - 1)
		neighbours[v - 1].add(u - 1)
	s = int(input()) - 1
	dists = bfs(n, neighbours, s)
	print(' '.join([str(dists[x]) for x in range(n) if x != s]))


def bfs(graph, queue, nondiscovered, results):
	while queue and nondiscovered:
		vertex = queue.pop(0)
		for adjacent in nondiscovered - graph[vertex]:
			results[adjacent] = results[vertex] + 1
			nondiscovered.remove(adjacent)
			queue.append(adjacent)
numCases = int(input())
for q in range(numCases):
	info = input().split(' ')
	numNodes = int(info[0])
	numMain = int(info[1])
	graph = {}
	nondiscovered = set()
	for x in range(numNodes):
		nondiscovered.add(x + 1)
	for x in range(numNodes):
		graph[x + 1] = set()
	for edge in range(numMain):
		info = input().split(' ')
		graph[int(info[0])].add(int(info[1]))
		graph[int(info[1])].add(int(info[0]))
	start = int(input())
	results = [0] * (numNodes + 1)
	queue = [start]
	nondiscovered.remove(start)
	bfs(graph, queue, nondiscovered, results)
	answer = ''
	for x in range(len(results)):
		if x != 0 and x != start:
			answer += str(results[x]) + ' '
	print(answer)


def bfs_dists(N, vertices, edges, u):
	dists = [0] * (N + 1)
	queue = [(u, 0)]
	not_visited = vertices - {u}
	while queue:
		(v, d) = queue.pop(0)
		visited = set()
		for n in not_visited:
			if (v, n) in edges:
				continue
			else:
				dists[n] = d + 1
				visited.add(n)
				queue.append((n, d + 1))
		not_visited = not_visited - visited
	return dists
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	vertices = set(range(1, N + 1))
	edges = set()
	for _ in range(M):
		(u, v) = map(int, input().split(' '))
		(e, e_) = ((u, v), (v, u))
		edges.add(e)
		edges.add(e_)
	S = int(input())
	dists = bfs_dists(N, vertices, edges, S)
	print(*[dists[i] for i in range(1, N + 1) if i != S])


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


def getDist(graph, S):
	result = [None] * len(graph)
	visited = set([S])
	nodes = range(1, len(graph))
	q = [(S, 0)]
	while q:
		(node, distance) = q.pop(0)
		toCheck = set()
		for i in nodes:
			if i not in visited and i not in graph[node]:
				visited.add(i)
				result[i] = distance + 1
				toCheck.add(i)
		if len(visited) == len(graph) - 1:
			break
		for i in toCheck:
			q.append((i, distance + 1))
	result.pop(S)
	return [str(i) for i in result[1:]]
q = int(input().strip())
for a0 in range(q):
	(N, M) = [int(s) for s in input().strip().split(' ')]
	graph = [set() for i in range(N + 1)]
	for a1 in range(M):
		(x, y) = [int(s) for s in input().strip().split(' ')]
		graph[x].add(y)
		graph[y].add(x)
	S = int(input().strip())
	result = getDist(graph, S)
	print(' '.join(result))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adj[u].add(v)
		adj[v].add(u)
	s = int(input()) - 1
	dist = [1 for _ in range(n)]
	dist[s] = 0
	unvisited = adj[s]
	newvisits = set()
	cd = 2
	while len(unvisited) > 0:
		for current in unvisited:
			neigh = adj[current]
			if len(unvisited | neigh) < n:
				dist[current] = cd
				newvisits.add(current)
		unvisited = unvisited - newvisits
		newvisits = set()
		cd += 1
	print(*[dist[x] for x in range(n) if x != s], sep=' ')


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


t = int(input())
for i in range(t):
	(c, r) = list(map(int, input().split()))
	e = {i: set() for i in range(1, c + 1)}
	unvisited = set(range(1, c + 1))
	for j in range(r):
		(f, t) = list(map(int, input().split()))
		e[f].add(t)
		e[t].add(f)
	s = int(input())
	d = {j: 0 for j in range(1, c + 1)}
	q = [(s, 0)]
	while q and unvisited:
		(node, incr) = q.pop(0)
		d[node] = incr
		for k in list(unvisited):
			if k not in e[node] and k != node:
				unvisited.remove(k)
				d[k] = incr + 1
				q.append((k, incr + 1))
	for j in range(1, c + 1):
		if j != s:
			print(d[j], end=' ')
	print()


def solve(start, nodes, adj):
	queue = [start]
	distances = {start: 0}
	snodes = set(nodes)
	snodes.remove(start)
	while len(queue) and len(snodes):
		curr = queue.pop(0)
		curr_d = distances[curr]
		for nei in snodes - adj[curr]:
			snodes.remove(nei)
			distances[nei] = curr_d + 1
			queue.append(nei)
	nodes.remove(start)
	print(' '.join(map(str, (distances[x] for x in nodes))))
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	nodes = list(range(1, n + 1))
	adj = {x: set() for x in nodes}
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a].add(b)
		adj[b].add(a)
	start = int(input())
	solve(start, nodes, adj)


def bfs(adj, start, nodes):
	queue = []
	visited = set()
	queue.append(start)
	visited.add(start)
	distances = [0] * len(nodes)
	while queue and len(visited) != len(nodes):
		node = queue.pop()
		to_visit = nodes - adj[node] - visited
		for neighbor in to_visit:
			queue.append(neighbor)
			visited.add(neighbor)
			distances[neighbor - 1] = distances[node - 1] + 1
	distances.pop(start - 1)
	return distances
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	nodes = set(range(1, n + 1))
	adj = {k: set() for k in range(1, n + 1)}
	for j in range(m):
		(n1, n2) = map(int, input().split())
		adj[n1].add(n2)
		adj[n2].add(n1)
	start = int(input())
	print(*bfs(adj, start, nodes))


from collections import deque

class Graph:

	def __init__(self, nodes):
		self.nodes = nodes
		self.conn = [set() for i in range(nodes)]

	def connect(self, a, b):
		self.conn[a].add(b)

	def distances(self, starting_point):
		LEVEL_UP = -1
		level = 0
		distances = [0] * self.nodes
		non_visited = set(range(self.nodes))
		queue = deque()
		queue.append(starting_point)
		queue.append(LEVEL_UP)
		non_visited.remove(starting_point)
		while queue:
			target = queue.popleft()
			if target == LEVEL_UP:
				if queue:
					queue.append(LEVEL_UP)
					level += 1
				continue
			distances[target] = level
			for node in non_visited.copy():
				if node not in self.conn[target]:
					queue.append(node)
					non_visited.remove(node)
		return distances
test_cases = int(input())
for i in range(test_cases):
	(n, m) = map(int, input().split())
	graph = Graph(n)
	for j in range(m):
		(x, y) = map(int, input().split())
		graph.connect(x - 1, y - 1)
		graph.connect(y - 1, x - 1)
	start = int(input())
	distances = graph.distances(start - 1)
	print(' '.join((str(d) for d in distances if d != 0)))


for _ in range(int(input())):
	(N, E) = map(int, input().split(' '))
	(V, M, ES, cp, cn, LN) = ([[0, 0] for _ in range(N + 1)], [1] * (N + 1), [None] * E, 0, 0, [None] * (E + E))
	for i in range(E):
		(u, v) = map(int, input().split(' '))
		ES[i] = (u, v)
		V[u][1] += 1
		V[v][1] += 1
	S = int(input())
	for i in range(1, N + 1):
		V[i][0] = V[i - 1][0] + V[i - 1][1]
		V[i - 1][1] = V[i - 1][0]
	(V[N][1], M[S]) = (V[N][0], 0)
	for (u, v) in ES:
		LN[V[u][1]] = v
		LN[V[v][1]] = u
		V[u][1] += 1
		V[v][1] += 1
	(s1, cs) = (set(), 2)
	for i in range(V[S][0], V[S][1]):
		s1.add(LN[i])
		M[LN[i]] = 1
	while s1.__len__():
		s3 = set()
		os1s = N - s1.__len__()
		for s1v in s1:
			s1ls = V[s1v][1] - V[s1v][0]
			if s1ls < os1s:
				M[s1v] = cs
			else:
				for i in range(V[s1v][0], V[s1v][1]):
					if LN[i] in s1:
						s1ls -= 1
						if s1ls < os1s:
							M[s1v] = cs
							break
			if M[s1v] != cs:
				s3.add(s1v)
		s1 = s3
		cs += 1
	rs = ''
	for i in range(1, N + 1):
		if i != S:
			if rs:
				rs += ' '
			rs += str(M[i])
	print(rs)


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import os
import sys
tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import os
import sys
tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import os
import sys
tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import os
import sys
tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))


import heapq
ps = heapq.heappush
pp = heapq.heappop
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [set() for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u - 1].add(v - 1)
		g[v - 1].add(u - 1)
	s = int(input()) - 1
	a = dict()
	Q = []
	ps(Q, (0, s))
	v = {s}
	while len(Q) != 0:
		(d, nd) = pp(Q)
		if nd not in a:
			a[nd] = d
		for adj in range(n):
			if adj not in g[nd] and adj not in v:
				ps(Q, (d + 1, adj))
				v.add(adj)
				if adj not in a:
					a[adj] = d + 1
				if len(a) == n:
					break
		if len(a) == n:
			break
	for ds in a:
		if a[ds] != 0:
			print(a[ds], end=' ')
	print()


tests = int(input())
for _ in range(tests):
	[n, e] = [int(i) for i in input().split(' ')]
	dists = [1] * n
	roads = {}
	for _ in range(e):
		[n1, n2] = [int(i) for i in input().split(' ')]
		if n1 not in roads:
			roads[n1] = set()
		if n2 not in roads:
			roads[n2] = set()
		roads[n1].add(n2)
		roads[n2].add(n1)
	start_loc = int(input())
	not_visited = roads[start_loc] if start_loc in roads else set()
	newly_visited = set()
	curr_dist = 2
	while len(not_visited) > 0:
		for i in not_visited:
			diff = not_visited | roads[i]
			if len(diff) < n:
				dists[i - 1] = curr_dist
				newly_visited.add(i)
		not_visited = not_visited - newly_visited
		newly_visited = set()
		curr_dist += 1
	del dists[start_loc - 1]
	print(' '.join((str(i) for i in dists)))