There are $n$ cities in Berland. The city numbered $1$ is the capital. Some pairs of cities are connected by a one-way road of length 1.

Before the trip, Polycarp for each city found out the value of $d_i$ — the shortest distance from the capital (the $1$-st city) to the $i$-th city.

Polycarp begins his journey in the city with number $s$ and, being in the $i$-th city, chooses one of the following actions:

Travel from the $i$-th city to the $j$-th city if there is a road from the $i$-th city to the $j$-th and $d_i < d_j$;

Travel from the $i$-th city to the $j$-th city if there is a road from the $i$-th city to the $j$-th and $d_i \geq d_j$;

Stop traveling.

Since the government of Berland does not want all people to come to the capital, so Polycarp no more than once can take the second action from the list. in other words, he can perform the second action $0$ or $1$ time during his journey. Polycarp, on the other hand, wants to be as close to the capital as possible.

For example, if $n = 6$ and the cities are connected, as in the picture above, then Polycarp could have made the following travels (not all possible options):

$2 \rightarrow 5 \rightarrow 1 \rightarrow 2 \rightarrow 5$;

$3 \rightarrow 6 \rightarrow 2$;

$1 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 5$.

Polycarp wants for each starting city $i$ to find out how close he can get to the capital. More formally: he wants to find the minimal value of $d_j$ that Polycarp can get from the city $i$ to the city $j$ according to the rules described above.


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers $n$ ($2 \leq n \leq 2 \cdot 10^5$) and $m$ ($1 \leq m \leq 2 \cdot 10^5$) — number of cities and roads, respectively.

This is followed by $m$ lines describing the roads. Each road is characterized by two integers $u$ and $v$ ($1 \leq u, v \leq n, u \ne v$) — the numbers of cities connected by a one-way road.

It is guaranteed that the sums of $n$ and $m$ over all test cases do not exceed $2 \cdot 10^5$.

It is guaranteed that for each pair of different cities $(u, v)$ there is at most one road from $u$ to $v$ (but a pair of roads from $u$ to $v$ and from $v$ to $u$ — is valid).

It is guaranteed that there is a path from the capital to all cities.


-----Output-----

For each test case, on a separate line output $n$ numbers, the $i$-th of which is equal to the minimum possible distance from the capital to the city where Polycarp ended his journey.


-----Examples-----

Input
3

6 7
1 2
1 3
2 5
2 4
5 1
3 6
6 2

2 2
1 2
2 1

6 8
1 2
1 5
2 6
6 1
2 3
3 4
4 2
5 4
Output
0 0 1 2 0 1 
0 0 
0 0 2 1 1 0


-----Note-----

None

Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Graph traversal

Shortest paths
Skill types: Dynamic programming

Starter code:

Solutions:
import sys, io, os
from collections import defaultdict
from heapq import heappush, heappop
if os.environ['USERNAME'] == 'kissz':
	inp = open('in2.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	inp()
	neighbors = defaultdict(list)
	(n, m) = map(int, inp().split())
	for i in range(m):
		(u, v) = map(int, inp().split())
		neighbors[u].append(v)
	dists = {1: 0}
	Q = []
	heappush(Q, (0, 1))
	while Q:
		(dist, node) = heappop(Q)
		if dists[node] == dist:
			for next_node in neighbors[node]:
				if next_node not in dists or dists[next_node] > dist + 1:
					dists[next_node] = dist + 1
					heappush(Q, (dist + 1, next_node))
	sol = {k: v for (k, v) in dists.items()}
	falls = []
	climbs = defaultdict(list)
	for (node, next_nodes) in neighbors.items():
		for next_node in next_nodes:
			if dists[node] < dists[next_node]:
				climbs[next_node].append(node)
			elif dists[node] > dists[next_node]:
				falls.append((dists[next_node], node))
	debug(neighbors)
	debug(climbs)
	debug(falls)
	debug(sol)
	for (dist, fall_node) in sorted(falls):
		debug(dist, fall_node)
		if sol[fall_node] > dist:
			sol[fall_node] = dist
			Q = [fall_node]
			while Q:
				node = Q.pop()
				for prev_node in climbs[node]:
					if sol[prev_node] > dist:
						sol[prev_node] = dist
						Q.append(prev_node)
		debug(sol)
	print(*[sol[i] for i in range(1, n + 1)])


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(d, visit, node, dp, high):
	visit[node] = True
	dp[node] = high[node]
	for x in d[node]:
		if not visit[x] and high[node] < high[x]:
			yield dfs(d, visit, x, dp, high)
		if high[node] < high[x]:
			dp[node] = min(dp[node], dp[x])
		else:
			dp[node] = min(dp[node], high[x])
	yield

def main():
	try:
		Extra = Sn()
		d = defaultdict(list)
		(n, m) = In()
		for i in range(m):
			(a, b) = In()
			d[a].append(b)
		high = [-1] * (n + 1)
		q = deque([1])
		high[1] = 0
		while q:
			node = q.popleft()
			for x in d[node]:
				if high[x] == -1:
					high[x] = high[node] + 1
					q.append(x)
		dp = [0] * (n + 1)
		visit = [False] * (n + 1)
		dfs(d, visit, 1, dp, high)
		print(*dp[1:])
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


import sys
input = sys.stdin.readline
from collections import deque

class Graph:

	def __init__(self, N, M=False):
		self.V = N
		if M:
			self.E = M
		self.edge = [[] for _ in range(self.V)]
		self.visited = [False] * self.V

	def add_edges(self, ind=1, bi=False):
		self.edges = [0] * self.E
		for i in range(self.E):
			(a, b) = map(int, input().split())
			a -= ind
			b -= ind
			self.edge[a].append(b)
			self.edges[i] = (a, b)
			if bi:
				self.edge[b].append(a)

	def add_edge(self, a, b, bi=False):
		self.edge[a].append(b)
		if bi:
			self.edge[b].append(a)

	def bfs(self, start):
		d = deque([start])
		self.min_cost = [-1] * self.V
		self.min_cost[start] = 0
		while len(d) > 0:
			v = d.popleft()
			for w in self.edge[v]:
				if self.min_cost[w] == -1:
					self.min_cost[w] = self.min_cost[v] + 1
					d.append(w)
		return

	def dfs(self, start, cost, N):
		stack = deque([start])
		self.visited[start] = True
		ans[start] = min(ans[start], cost)
		while stack:
			v = stack.pop()
			for u in self.edge[v]:
				if self.visited[u]:
					continue
				stack.append(u)
				self.visited[u] = True
				ans[u % N] = min(ans[u % N], cost)
T = int(input())
for t in range(T):
	input()
	(N, M) = map(int, input().split())
	G = Graph(N, M)
	G.add_edges(ind=1, bi=False)
	G.bfs(0)
	costs = []
	for (i, cos) in enumerate(G.min_cost):
		costs.append((cos, i))
	costs.sort()
	G2 = Graph(N * 2)
	for (a, b) in G.edges:
		if G.min_cost[b] > G.min_cost[a]:
			G2.add_edge(b, a)
			G2.add_edge(N + b, N + a)
		else:
			G2.add_edge(b, a + N)
	ans = [N] * N
	for (cos, i) in costs:
		G2.dfs(i, cos, N)
	print(*ans, sep=' ')


from collections import defaultdict, deque
import copy
import heapq

def main():
	cases = int(input())
	ans_list = []
	for _ in range(cases):
		input()
		(n, m) = map(int, input().split(' '))
		(adj, inverse_adj) = (defaultdict(list), defaultdict(list))
		for i in range(m):
			(start, end) = map(int, input().split(' '))
			adj[start].append(end)
			inverse_adj[end].append(start)
		d = [-1 for i in range(n + 1)]
		temp_ans = [float('inf') for i in range(n + 1)]
		q = deque([1])
		d[1] = 0
		while len(q) > 0:
			cur = q.popleft()
			cur_dist = d[cur]
			temp_ans[cur] = min(temp_ans[cur], cur_dist)
			for edge in adj[cur]:
				if d[edge] != -1:
					temp_ans[cur] = min(d[edge], temp_ans[cur])
				else:
					d[edge] = cur_dist + 1
					q.append(edge)
		heap = [(val, i + 1) for (i, val) in enumerate(temp_ans[1:])]
		heapq.heapify(heap)
		final_ans = [float('inf') for i in range(n + 1)]
		while len(heap) > 0:
			(val, dfs_start) = heapq.heappop(heap)
			if final_ans[dfs_start] != float('inf'):
				continue
			final_ans[dfs_start] = val
			stack = [dfs_start]
			while len(stack) > 0:
				cur = stack.pop()
				for edge in inverse_adj[cur]:
					if final_ans[edge] == float('inf') and d[cur] > d[edge]:
						final_ans[edge] = val
						stack.append(edge)
		ans_list.append(final_ans[1:])
	for lst in ans_list:
		print(' '.join(list(map(str, lst))))
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	blank = input()
	(n, m) = map(int, input().split())
	dct = {i: [] for i in range(1, n + 1)}
	for times in range(m):
		(start, end) = map(int, input().split())
		dct[start].append(end)
	dis = {1: 0}
	stack = [1]
	iterate = [1]
	so = 1
	decoy = 0
	while so < n:
		decoy = stack.pop(0)
		for adj in dct[decoy]:
			if adj in dis:
				continue
			else:
				so += 1
				dis[adj] = dis[decoy] + 1
				iterate.append(adj)
				stack.append(adj)
	ans = [dis[i] for i in range(1, n + 1)]
	for node in iterate[::-1]:
		minn = dis[node]
		for adj in dct[node]:
			if dis[adj] <= dis[node]:
				minn = min(minn, dis[adj])
			else:
				minn = min(ans[adj - 1], minn)
		ans[node - 1] = minn
	print(*ans)


for _ in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adj[u].append(v)
	dis = [-1] * n
	dis[0] = 0
	que = [0]
	for i in range(n):
		u = que[i]
		for v in adj[u]:
			if dis[v] == -1:
				dis[v] = dis[u] + 1
				que.append(v)
	ans = [0] * n
	for u in sorted([i for i in range(n)], key=lambda x: dis[x], reverse=True):
		ans[u] = dis[u]
		for v in adj[u]:
			if dis[u] >= dis[v]:
				ans[u] = min(ans[u], dis[v])
			else:
				ans[u] = min(ans[u], ans[v])
	print(*ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		dist = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					dist[i] = dist[element] + 1
					vis[i] = 1
		return dist

	def dfs(self, root, minn):
		ans = [i for i in minn]
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = minn[element]
			for i in self.graph[element]:
				if i != self.parent[element]:
					m = min(m, ans[i])
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0] * self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i] == 0:
				q.append(i)
		while len(q) != 0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if vis != self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def eulertour(self, root):
		stack = [root]
		t = []
		while len(stack) != 0:
			element = stack[-1]
			if vis[element]:
				t.append(stack.pop())
				continue
			t.append(element)
			vis[element] = 1
			for i in self.graph[element]:
				if not vis[i]:
					stack.append(i)
		return t
for nt in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	adj = [[] for xy in range(n)]
	for xy in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adj[u].append(v)
	dis = [-1] * n
	dis[0] = 0
	que = [0]
	for i in range(n):
		u = que[i]
		for v in adj[u]:
			if dis[v] == -1:
				dis[v] = dis[u] + 1
				que.append(v)
	ans = [0] * n
	for u in sorted([i for i in range(n)], key=lambda x: dis[x], reverse=True):
		ans[u] = dis[u]
		for v in adj[u]:
			if dis[u] >= dis[v]:
				ans[u] = min(ans[u], dis[v])
			else:
				ans[u] = min(ans[u], ans[v])
	print(*ans)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import heapq
INF = 10 ** 9

def Dijkstra(graph, start):
	dist = [INF] * len(graph)
	parent = [INF] * len(graph)
	queue = [(0, start)]
	while queue:
		(path_len, v) = heapq.heappop(queue)
		if dist[v] == INF:
			dist[v] = path_len
			for w in graph[v]:
				if dist[w[0]] == INF:
					parent[w[0]] = v
					heapq.heappush(queue, (dist[v] + w[1], w[0]))
	return (dist, parent)
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	graph = []
	for i in range(n):
		graph.append([])
	edges = []
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x - 1].append([y - 1, 1])
		edges.append([x - 1, y - 1])
	(dist, parent) = Dijkstra(graph, 0)
	visited = set()
	mindist = [INF] * n
	for i in range(n):
		mindist[i] = dist[i]
		for j in graph[i]:
			mindist[i] = min(mindist[i], dist[j[0]])
	graph2 = []
	for i in range(n):
		graph2.append([])
	edges2 = []
	for edge in edges:
		x = edge[0]
		y = edge[1]
		if dist[y] > dist[x]:
			graph2[x].append(y)
			edges2.append([x, y])
	vertices = []
	for i in range(n):
		vertices.append([dist[i], i])
	vertices.sort()
	vertices.reverse()
	for i in range(n):
		index = vertices[i][1]
		for j in graph2[index]:
			mindist[index] = min(mindist[index], mindist[j])
	for i in range(n):
		mindist[i] = str(mindist[i])
	print(' '.join(mindist))


import sys
input = sys.stdin.buffer.readline
from collections import deque

def prog():
	for _ in range(int(input())):
		lol = input()
		(n, m) = map(int, input().split())
		ans = [0] * n
		adj = [[] for i in range(n)]
		radj = [[] for i in range(n)]
		d = [0] * n
		min_d = []
		for i in range(m):
			(u, v) = map(int, input().split())
			u -= 1
			v -= 1
			adj[u].append(v)
			radj[v].append(u)
		q = deque([0])
		vis = [0] * n
		vis[0] = 1
		while q:
			c = q.popleft()
			for ne in adj[c]:
				if not vis[ne]:
					vis[ne] = 1
					d[ne] = d[c] + 1
					q.append(ne)
		for i in range(n):
			min_d.append([d[i], i])
		min_d.sort()
		vis = [0] * n
		for i in min_d:
			if not vis[i[1]]:
				vis[i[1]] = 1
				ans[i[1]] = i[0]
			for ne in radj[i[1]]:
				if not vis[ne] and d[ne] >= d[i[1]]:
					q.append(ne)
					vis[ne] = 1
			while q:
				c = q.popleft()
				ans[c] = i[0]
				for ne in radj[c]:
					if not vis[ne] and d[ne] < d[c]:
						vis[ne] = 1
						q.append(ne)
		print(*ans)
prog()


class PrioQueueError(ValueError):
	pass

class PrioQueue:

	def __init__(self, elist=None):
		if elist is None:
			elist = []
		self._elems = list(elist)
		if elist:
			self.buildheap()

	def is_empty(self):
		return not self._elems

	def peek(self):
		if self.is_empty():
			raise PrioQueueError('in peek')
		return self._elems[0]

	def enqueue(self, e):
		self._elems.append(e)
		self.siftup(e, len(self._elems) - 1)

	def siftup(self, e, last):
		(elem, i, j) = (self._elems, last, (last - 1) // 2)
		while j >= 0 and elem[i] < elem[j]:
			(elem[i], elem[j]) = (elem[j], elem[i])
			(i, j) = (j, (j - 1) // 2)

	def dequeue(self):
		if self.is_empty():
			raise PrioQueueError('in dequeue')
		e0 = self._elems[0]
		e = self._elems.pop()
		if len(self._elems) > 0:
			self.siftdown(e, len(self._elems) - 1)
		return e0

	def siftdown(self, e, end):
		(elem, i, j) = (self._elems, 0, 1)
		while j <= end:
			if j + 1 <= end and elem[j + 1] < elem[j]:
				j += 1
			if e <= elem[j]:
				break
			elem[i] = elem[j]
			(i, j) = (j, j * 2 + 1)
		elem[i] = e

	def buildheap(self):
		end = len(self._elems)
		for i in range(end // 2, -1, -1):
			self.siftdown(self._elems[i], -1)

class QNode:

	def __init__(self, _elem, _next=None):
		self._elem = _elem
		self._next = _next

class CQueue:

	def __init__(self):
		self._rear = None

	def enqueue(self, _elem):
		if self.is_empty():
			self._rear = QNode(_elem)
			self._rear._next = self._rear
		else:
			q = QNode(_elem)
			q._next = self._rear._next
			self._rear._next = q
			self._rear = q

	def dequeue(self):
		if self.is_empty():
			raise ValueError('in dequeue')
		q = self._rear._next._elem
		if self._rear._next is self._rear:
			self._rear = None
		else:
			self._rear._next = self._rear._next._next
		return q

	def is_empty(self):
		return self._rear is None

def capital(n, roads):
	ways = [[] for i in range(n + 1)]
	deways = [[] for i in range(n + 1)]
	for r in roads:
		ways[r[0]].append(r[1])
	for r in roads:
		deways[r[1]].append(r[0])
	pathss = [-1] * (n + 1)
	cands = PrioQueue([(0, 1)])
	count = 0
	while count < n and (not cands.is_empty()):
		(plen, vj) = cands.dequeue()
		if pathss[vj] != -1:
			continue
		pathss[vj] = plen
		for vjj in ways[vj]:
			if pathss[vjj] == -1:
				cands.enqueue((plen + 1, vjj))
		count += 1
	jumpCity = {}
	for i in range(1, n + 1):
		for citt in ways[i]:
			if i not in jumpCity:
				if pathss[i] - pathss[citt] > 0:
					jumpCity[i] = pathss[citt]
			elif pathss[citt] < jumpCity[i]:
				jumpCity[i] = pathss[citt]
	minpaths = pathss.copy()
	jumpit = jumpCity.items()
	for (toCity, jumpwhere) in jumpit:
		cq = CQueue()
		cq.enqueue(toCity)
		while not cq.is_empty():
			ptc = cq.dequeue()
			if jumpwhere < minpaths[ptc]:
				minpaths[ptc] = jumpwhere
			for tptc in deways[ptc]:
				if pathss[ptc] > pathss[tptc] > jumpwhere:
					cq.enqueue(tptc)
	return minpaths
t = int(input())
for qwq in range(t):
	input()
	inp = input().split()
	(n, roadnum) = (int(inp[0]), int(inp[1]))
	roads = []
	for i in range(roadnum):
		roads.append(tuple(map(int, input().split())))
	ans = capital(n, roads)
	for i in range(1, len(ans)):
		print(ans[i], end=' ')
	print()


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		input()
		(n, m) = map(int, input().split())
		adj = [[] for _ in range(n)]
		for _ in range(m):
			(u, v) = map(lambda x: int(x) - 1, input().split())
			adj[u].append(v)
		dis = [-1] * n
		dis[0] = 0
		que = [0]
		for i in range(n):
			u = que[i]
			for v in adj[u]:
				if dis[v] == -1:
					dis[v] = dis[u] + 1
					que.append(v)
		que = sorted([i for i in range(n)], key=lambda x: dis[x], reverse=True)
		ans = [n] * n
		for u in que:
			ans[u] = dis[u]
			for v in adj[u]:
				if dis[u] >= dis[v]:
					ans[u] = min(ans[u], dis[v])
				else:
					ans[u] = min(ans[u], ans[v])
		print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from sys import stdin
from collections import deque

def NC_Dij(lis, start):
	ret = [float('inf')] * len(lis)
	ret[start] = 0
	q = deque([start])
	plis = [i for i in range(len(lis))]
	while len(q) > 0:
		now = q.popleft()
		for nex in lis[now]:
			if ret[nex] > ret[now] + 1:
				ret[nex] = ret[now] + 1
				plis[nex] = now
				q.append(nex)
	return (ret, plis)
tt = int(stdin.readline())
for loop in range(tt):
	stdin.readline()
	(n, m) = map(int, stdin.readline().split())
	lis = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, stdin.readline().split())
		u -= 1
		v -= 1
		lis[u].append(v)
	(dlis, tmp) = NC_Dij(lis, 0)
	dind = []
	for i in range(n):
		dind.append((dlis[i], i))
	dind.sort()
	dind.reverse()
	ans = [None] * n
	for (nd, ind) in dind:
		now = nd
		for nex in lis[ind]:
			if dlis[nex] > nd:
				now = min(now, ans[nex])
			else:
				now = min(now, dlis[nex])
		ans[ind] = now
	print(*ans)


from collections import defaultdict, deque
import sys
input = sys.stdin.readline

def get_distances(graph):
	q = deque()
	q.append(1)
	q.append(None)
	(d, distances) = (0, {})
	while len(q) > 1:
		u = q.popleft()
		if u is None:
			d += 1
			q.append(None)
			continue
		if u in distances:
			continue
		distances[u] = d
		for v in graph[u]:
			if v not in distances:
				q.append(v)
	return distances

def bfs(starting_vertex, graph, visited, dists):
	q = deque()
	q.append((starting_vertex, None))
	q.append((None, None))
	(d, nodes_at_d) = (0, defaultdict(list))
	while len(q) > 1:
		(u, parent) = q.popleft()
		if u is None:
			d += 1
			q.append((None, None))
			continue
		nodes_at_d[d].append((u, parent))
		if u in visited:
			continue
		visited.add(u)
		for v in graph[u]:
			if v not in visited:
				q.append((v, u))
			else:
				dists[u] = min(dists[u], dists[v])
	while d >= 0:
		for (u, parent) in nodes_at_d[d]:
			if parent is not None:
				dists[parent] = min(dists[parent], dists[u])
		d -= 1
t = int(input())
for _ in range(t):
	_ = input()
	(n, m) = (int(i) for i in input().split(' '))
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = (int(i) for i in input().split(' '))
		graph[u].append(v)
	dists = get_distances(graph)
	new_graph = defaultdict(list)
	for u in graph:
		while graph[u]:
			v = graph[u].pop()
			if dists[v] > dists[u]:
				new_graph[u].append(v)
				new_graph[u + n].append(v + n)
			else:
				new_graph[u].append(v + n)
	for u in range(1, n + 1):
		dists[u + n] = dists[u]
	visited = set()
	bfs(1, new_graph, visited, dists)
	for u in range(1, n + 1):
		print(min(dists[u], dists[u + n]), end=' ')
	print()


import collections
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	graph = collections.defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
	dist = collections.defaultdict(int)
	q = collections.deque([(1, 0)])
	d0 = collections.defaultdict(list)
	maxdist = 0
	while q:
		(node, d) = q.popleft()
		if node in dist:
			continue
		maxdist = max(maxdist, d)
		dist[node] = d
		d0[d].append(node)
		for v in graph[node]:
			q.append((v, d + 1))
	nomod = collections.defaultdict(int)
	for i in range(1, n + 1):
		nomod[i] = dist[i]
	best = collections.defaultdict(lambda : n)
	for i in range(1, n + 1):
		best[i] = dist[i]
		for edge in graph[i]:
			best[i] = min(best[i], dist[edge])
	nomod[1] = 0
	access = set()
	for d in range(maxdist, 0, -1):
		for node in d0[d]:
			for edge in graph[node]:
				if edge not in access:
					continue
				best[node] = min(best[node], best[edge])
		for node in d0[d]:
			access.add(node)
	arr = [0] * n
	for i in range(1, n + 1):
		arr[i - 1] = best[i]
	print(' '.join(map(str, arr)))


from sys import stdin
t = int(stdin.readline())

def graph_add(graph, key, value):
	if key in graph:
		graph[key].append(value)
	else:
		graph[key] = [value]
for _ in range(t):
	stdin.readline()
	L = [int(x) for x in stdin.readline().split(' ')]
	(n, m) = (L[0], L[1])
	graph = {}
	for _ in range(m):
		L = [int(x) for x in stdin.readline().split(' ')]
		(u, v) = (L[0], L[1])
		graph_add(graph, u, v)
	d = {}
	stack = [(1, 0)]
	while len(stack) > 0:
		(vertex, distance) = stack.pop()
		for neighbor in graph.get(vertex, []):
			if distance + 1 < d.get(neighbor, n):
				stack.append((neighbor, distance + 1))
		prev_distance = d.get(vertex, n)
		d[vertex] = min(prev_distance, distance)
	dist_to_vertex = []
	for (k, v) in d.items():
		dist_to_vertex.append((v, k))
	dist_to_vertex = sorted(dist_to_vertex)[::-1]
	res = {}
	for (distance, vertex) in dist_to_vertex:
		curr_dist = d[vertex]
		for neighbor in graph.get(vertex, []):
			curr_dist = min(curr_dist, d[neighbor])
			if d[vertex] < d[neighbor]:
				curr_dist = min(curr_dist, res[neighbor])
		res[vertex] = curr_dist
	tmp = []
	for i in range(1, n + 1):
		tmp.append(str(res[i]))
	print(' '.join(tmp))


from heapq import heapify, heappop, heappush

def solve():
	input()
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	G_rev = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = [int(t) - 1 for t in input().split()]
		G[u].append(v)
		G_rev[v].append(u)
	root = 0
	dist = [0] * n
	queue = [root]
	visited = [0] * n
	visited[root] = 1
	for u in queue:
		for v in G[u]:
			if not visited[v]:
				visited[v] = 1
				queue.append(v)
				dist[v] = dist[u] + 1
	ans = dist.copy()
	for u in range(n):
		for v in G_rev[u]:
			ans[v] = min(ans[v], dist[u])
	pq = [(ans[v], v) for v in range(n)]
	heapify(pq)
	visited = [0] * n
	done = 0
	while done < n:
		(d, u) = heappop(pq)
		if visited[u]:
			continue
		done += 1
		ans[u] = d
		visited[u] = 1
		for v in G_rev[u]:
			if not visited[v] and dist[v] < dist[u]:
				heappush(pq, (d, v))
	print(*ans)
import sys, os, io
input = lambda : sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode('ascii'))
for _ in range(int(input())):
	solve()
os.write(1, stdout.getvalue())


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *

def Dijkstra(s, n, adj):
	dist = [10000000] * (n + 1)
	dist[s] = 0
	heap = [(0, s)]
	while heap:
		(d, u) = heappop(heap)
		if d != dist[u]:
			continue
		for v in adj[u]:
			nd = d + 1
			if nd < dist[v]:
				dist[v] = nd
				heappush(heap, (nd, v))
	return dist

def dfs(u, k):
	if dist[u] <= k:
		return dist[u]
	if res[u] < n:
		return res[u]
	res[u] = dist[u]
	for v in dic[u]:
		res[u] = min(res[u], dfs(v, dist[u]))
	return res[u]
for i in range(N()):
	input()
	(n, m) = RL()
	dic = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = RL()
		dic[u].append(v)
	dist = Dijkstra(1, n, dic)
	deep = sorted([(dist[i], i) for i in range(2, n + 1)], key=lambda x: x[0], reverse=True)
	res = [n] * (n + 1)
	res[1] = 0
	for (_, u) in deep:
		res[u] = dfs(u, -1)
	print_list(res[1:])


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
from itertools import repeat

def line():
	return map(int, input().split())

def num():
	return int(input())

def nfunc(f, n, *args, **kwargs):
	return (f(*args, **kwargs) for _ in repeat(None, n))

class Node:

	def __init__(self, x):
		self.x = x
		self.ins = []
		self.outs = []

	def path(self, other):
		self.outs.append(other)
		other.ins.append(self)
t = num()
for _ in repeat(None, t):
	input()
	(n, m) = line()
	nodes = [Node(i) for i in range(n)]
	for (u, v) in nfunc(line, m):
		nodes[u - 1].path(nodes[v - 1])
	ds = [0] * n
	done = set()
	q = [nodes[0]]
	levels = []
	i = 0
	while q:
		nq = []
		for u in q:
			if u not in done:
				done.add(u)
				ds[u.x] = i
				nq.extend(u.outs)
		levels.append(q)
		q = nq
		i += 1
	bests = ds.copy()
	for level in levels[::-1]:
		for u in level:
			for v in u.outs:
				if ds[u.x] < ds[v.x]:
					bests[u.x] = min(bests[u.x], bests[v.x])
				else:
					bests[u.x] = min(bests[u.x], ds[v.x])
	print(' '.join(map(str, bests)))


import sys
input = sys.stdin.readline
from collections import deque
from operator import itemgetter
t = int(input())
for tests in range(t):
	_ = input().strip()
	(n, m) = map(int, input().split())
	E = [[] for i in range(n + 1)]
	E_INV = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		E[x].append(y)
		E_INV[y].append(x)
	ANS = [1 << 30] * (n + 1)
	D = [1 << 30] * (n + 1)
	D[1] = 0
	Q = deque([1])
	while Q:
		x = Q.popleft()
		for to in E[x]:
			if D[to] > D[x] + 1:
				D[to] = D[x] + 1
				Q.append(to)
	for i in range(n + 1):
		ANS[i] = min(ANS[i], D[i])
		for to in E_INV[i]:
			ANS[to] = min(ANS[to], D[i])
	D2 = [(d, i) for (i, d) in enumerate(D)]
	D2.sort(key=itemgetter(0), reverse=True)
	for (d, i) in D2:
		for to in E[i]:
			if D[to] > D[i]:
				ANS[i] = min(ANS[i], ANS[to])
	print(*ANS[1:])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve():
	x = input()
	(N, M) = getInts()
	graph = dd(set)
	for m in range(M):
		(U, V) = getInts()
		U -= 1
		V -= 1
		graph[U].add(V)
	D = [0] * N

	def bfs(node):
		queue = dq([])
		queue.append((node, 0))
		visited = set()
		visited.add(node)
		while queue:
			(node, level) = queue.popleft()
			for neigh in graph[node]:
				if neigh not in visited:
					D[neigh] = level + 1
					visited.add(neigh)
					queue.append((neigh, level + 1))
	bfs(0)
	visited = set()
	ans = [0] * N

	@bootstrap
	def dfs(node):
		visited.add(node)
		ans[node] = D[node]
		for neigh in graph[node]:
			if neigh not in visited and D[node] < D[neigh]:
				yield dfs(neigh)
			if D[node] < D[neigh]:
				ans[node] = min(ans[node], ans[neigh])
			else:
				ans[node] = min(ans[node], D[neigh])
		yield
	dfs(0)
	print(*ans)
	return
for _ in range(getInt()):
	solve()


import sys
input = sys.stdin.readline
from collections import *

def bfs():
	q = deque([0])
	dist = [-1] * n
	dist[0] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
for _ in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	edges = []
	for _ in range(m):
		(u, v) = map(int, input().split())
		G[u - 1].append(v - 1)
		edges.append((u - 1, v - 1))
	dist = bfs()
	m = [dist[v] for v in range(n)]
	for v in range(n):
		for nv in G[v]:
			m[v] = min(m[v], dist[nv])
	ins = [0] * n
	outs = defaultdict(list)
	for (u, v) in edges:
		if dist[u] < dist[v]:
			ins[v] += 1
			outs[u].append(v)
	q = deque([v for v in range(n) if ins[v] == 0])
	order = []
	while q:
		v = q.popleft()
		order.append(v)
		for nv in outs[v]:
			ins[nv] -= 1
			if ins[nv] == 0:
				q.append(nv)
	for v in order[::-1]:
		for nv in outs[v]:
			m[v] = min(m[v], m[nv])
	print(*m)


import io
import os
from collections import deque

def bfs(source, graph):
	q = deque([source])
	dist = {source: 0}
	while q:
		node = q.popleft()
		d = dist[node]
		for nbr in graph[node]:
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def solve(N, M, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
	D = bfs(0, graph)
	cache = [-1] * (2 * N)

	def dp(u, used):
		if u == 0:
			return 0
		key = (u << 1) + used
		if cache[key] == -1:
			best = D[u]
			for v in graph[u]:
				if D[u] < D[v]:
					best = min(best, dp(v, used))
				elif used:
					best = min(best, dp(v, 0))
			cache[key] = best
		return cache[key]
	keys = list(D.keys())
	for u in reversed(keys):
		dp(u, 0)
	for u in reversed(keys):
		dp(u, 1)
	return ' '.join((str(min(dp(u, 0), dp(u, 1))) for u in range(N)))
DEBUG = False
if DEBUG:
	import random
	N = 2 * 10 ** 5
	edges = []
	for i in range(N - 1):
		edges.append((i, i + 1))
		edges.append((i + 1, i))
	solve(N, len(edges), edges)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	input()
	(N, M) = [int(x) for x in input().split()]
	edges = [[int(x) - 1 for x in input().split()] for i in range(M)]
	ans = solve(N, M, edges)
	print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
for _ in range(inp()):
	__ = input()
	(n, m) = inpl()
	g = [[] for _ in range(n)]
	for __ in range(m):
		(a, b) = inpl()
		a -= 1
		b -= 1
		g[a].append(b)
	d = [INF] * n
	d[0] = 0
	q = deque([0])
	while q:
		now = q.popleft()
		for v in g[now]:
			if d[v] > d[now] + 1:
				d[v] = d[now] + 1
				q.append(v)
	q = deque([])
	res = d[:]
	dind = [(num, i) for (i, num) in enumerate(d)]
	dind.sort(reverse=True)
	for (D, i) in dind:
		for v in g[i]:
			if d[v] > d[i]:
				res[i] = min(res[i], res[v])
			else:
				res[i] = min(res[i], d[v])
	print(*res)


import sys
input = sys.stdin.buffer.readline
from queue import deque
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

@bootstrap
def dp(node, nMove2):
	if memo[node][nMove2] == None:
		ans = d[node]
		for nex in adj[node]:
			if d[node] < d[nex]:
				ans = min(ans, (yield dp(nex, nMove2)))
			elif nMove2 + 1 <= 1:
				ans = min(ans, (yield dp(nex, nMove2 + 1)))
		memo[node][nMove2] = ans
	yield memo[node][nMove2]
t = int(input())
allAns = []
for _ in range(t):
	input()
	(n, m) = [int(x) for x in input().split()]
	adj = [[] for _ in range(n + 1)]
	for __ in range(m):
		(u, v) = [int(x) for x in input().split()]
		adj[u].append(v)
	d = [0 for _ in range(n + 1)]
	visited = [False for _ in range(n + 1)]
	q = deque()
	q.append([1, 0])
	while q:
		(road, distance) = q.popleft()
		if visited[road] == True:
			continue
		d[road] = distance
		visited[road] = True
		for nex in adj[road]:
			if visited[nex] == False:
				q.append([nex, distance + 1])
	memo = [[None, None] for __ in range(n + 1)]
	ans = []
	for i in range(1, n + 1):
		ans.append(dp(i, 0))
	allAns.append(ans)
multiLineArrayOfArraysPrint(allAns)


from collections import defaultdict
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
t = int(input())

def bfs(g, depth, n, visited):
	index = 0
	q = []
	depth[1] = 0
	visited[1] = 1
	for child in g[1]:
		visited[child] = 1
		q.append((1, child))
	while True:
		if index >= n - 1:
			break
		(pa, node) = q[index]
		depth[node] = depth[pa] + 1
		for child in g[node]:
			if visited[child] != 1:
				visited[child] = 1
				q.append((node, child))
		index += 1

@bootstrap
def dfs(g, node, depth, dp, visited):
	visited[node] = 1
	min_val = depth[node]
	for child in g[node]:
		if depth[child] < depth[node]:
			min_val = min(min_val, depth[child])
		elif depth[child] > depth[node]:
			if visited[child] != 1:
				result = (yield dfs(g, child, depth, dp, visited))
				min_val = min(result, min_val)
			else:
				min_val = min(min_val, dp[child])
		else:
			min_val = min(depth[node], min_val)
	dp[node] = min_val
	yield min_val
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	g = defaultdict(set)
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].add(v)
	visited = [0 for i in range(n + 1)]
	depth = [0 for i in range(n + 1)]
	bfs(g, depth, n, visited)
	visited = [0 for i in range(n + 1)]
	dp = [1008600 for i in range(n + 1)]
	dfs(g, 1, depth, dp, visited)
	print(' '.join((str(i) for i in dp[1:])))


from collections import deque

def solution(n, m, edges):
	adj = [[] for _ in range(n)]
	dist = {}
	q = deque()
	sol = [10 ** 6 for _ in range(n)]
	for [u, v] in edges:
		adj[u - 1].append(v - 1)
	q.append((0, 0))
	dist[0] = 0
	while len(q) > 0:
		(u, d) = q.popleft()
		for v in adj[u]:
			if v not in dist or d + 1 < dist[v]:
				q.append((v, d + 1))
				dist[v] = d + 1
	verts = list(range(n))
	verts.sort(key=lambda u: dist[u], reverse=True)
	for u in verts:
		cur = dist[u]
		for v in adj[u]:
			if dist[u] < dist[v]:
				cur = min(cur, sol[v])
			else:
				cur = min(cur, dist[v])
		sol[u] = cur
	print(*sol)
T = int(input())
for t in range(1, T + 1):
	input()
	[n, m] = list(map(int, input().split()))
	edges = [list(map(int, input().split())) for _ in range(m)]
	solution(n, m, edges)


from array import array
from itertools import repeat

def solve():
	t = int(input())
	for _ in range(t):
		input()
		(n_cities, n_roads) = map(int, input().split())
		adjacency_list = [[] for _ in range(n_cities)]
		for _ in range(n_roads):
			(from_, to) = map(int, input().split())
			adjacency_list[from_ - 1].append(to - 1)
		distance = 0
		distances = array('i', repeat(-1, n_cities))
		level = {0}
		while level:
			next_level = set()
			for node in level:
				distances[node] = distance
			for node in level:
				for neighbor in adjacency_list[node]:
					if distances[neighbor] == -1:
						next_level.add(neighbor)
			distance += 1
			level = next_level
		memo = array('i', repeat(-1, n_cities))

		def helper(node):
			stack = [(node, True)]
			while stack:
				(node, enter) = stack.pop()
				if enter:
					if memo[node] == -1:
						memo[node] = distances[node]
						stack.append((node, False))
						for neighbor in adjacency_list[node]:
							if distances[node] < distances[neighbor]:
								stack.append((neighbor, True))
				else:
					min_distance = distances[node]
					for neighbor in adjacency_list[node]:
						if distances[node] < distances[neighbor]:
							min_distance = min(min_distance, memo[neighbor])
						else:
							min_distance = min(min_distance, distances[neighbor])
					memo[node] = min_distance
		for city in range(n_cities):
			helper(city)
		print(*(memo[city] for city in range(n_cities)))
solve()


import sys

def input():
	return sys.stdin.readline().strip()

def mint():
	return int(input())

def mints():
	return map(int, input().split())
for i in range(mint()):
	input()
	(n, m) = mints()
	n2 = n * 2
	e = [[] for i in range(n)]
	eb = [[] for i in range(n)]
	for i in range(m):
		(u, v) = mints()
		e[u - 1].append(v - 1)
		eb[v - 1].append(u - 1)
	q = [0]
	d = [None] * n
	d[0] = 0
	i = 0
	while i < len(q):
		x = q[i]
		i += 1
		for v in e[x]:
			if d[v] is None:
				d[v] = d[x] + 1
				q.append(v)
	idx = [None] * n
	for i in range(n):
		idx[i] = (d[i], i)
	idx.sort()
	q = []
	i = 0
	was = [[None] * n for _ in range(2)]
	ans = [int(2000000000.0)] * n
	for (_, id) in idx:
		dd = d[id]
		for s in range(2):
			if was[s][id] is None:
				was[s][id] = (-1, -1)
				q.append((id, s))
				ans[id] = min(ans[id], dd)
		while i < len(q):
			(x, s) = q[i]
			i += 1
			for v in eb[x]:
				if d[x] > d[v]:
					if was[s][v] is None:
						q.append((v, s))
						was[s][v] = (x, s)
						ans[v] = min(ans[v], dd)
				elif s == 1:
					if was[0][v] is None:
						q.append((v, 0))
						was[0][v] = (x, s)
						ans[v] = min(ans[v], dd)
	print(' '.join(map(str, ans)))


import sys
from collections import deque
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	unko = input()
	(n, m) = map(int, input().split())
	pre_edge = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		pre_edge[u - 1].append(v - 1)
	deq = deque([0])
	dist = [10 ** 17 for i in range(n)]
	dist[0] = 0
	edge = [[] for i in range(n)]
	while deq:
		v = deq.popleft()
		for nv in pre_edge[v]:
			if dist[nv] > dist[v] + 1:
				dist[nv] = dist[v] + 1
				edge[v].append(nv)
				deq.append(nv)
	dist_sort = [[] for i in range(n)]
	for i in range(n):
		dist_sort[dist[i]].append(i)
	ans = [dist[i] for i in range(n)]
	for d in range(n - 1, -1, -1):
		for v in dist_sort[d]:
			for nv in pre_edge[v]:
				if dist[nv] > dist[v]:
					ans[v] = min(ans[v], ans[nv])
				else:
					ans[v] = min(dist[nv], ans[v])
	print(*ans)


from sys import stdin, stdout
import math
from functools import reduce

def main():
	t = int(stdin.readline())
	for _ in range(t):
		empty_space = stdin.readline()
		(n, m) = list(map(int, stdin.readline().split()))
		g = [[] for _ in range(n + 1)]
		visited = [False for _ in range(n + 1)]
		dist = [0 for _ in range(n + 1)]
		for _ in range(m):
			(a, b) = list(map(int, stdin.readline().split()))
			g[a].append(b)
		stack = [1]
		visited[1] = True
		while stack:
			temp_stack = []
			for x in stack:
				for y in g[x]:
					if visited[y]:
						continue
					temp_stack.append(y)
					dist[y] = dist[x] + 1
					visited[y] = True
			stack = temp_stack
		visited = [False for _ in range(n + 1)]
		stack = [1]
		new_g = [1]
		visited[1] = True
		while stack:
			temp_stack = []
			for x in stack:
				for y in g[x]:
					if visited[y] or dist[y] <= dist[x]:
						continue
					temp_stack.append(y)
					visited[y] = True
					new_g.append(y)
			stack = temp_stack
		ans = [dist[i] for i in range(n + 1)]
		for x in reversed(new_g):
			for y in g[x]:
				if dist[y] > dist[x]:
					ans[x] = min(ans[y], ans[x])
				else:
					ans[x] = min(dist[y], ans[x])
		stdout.write(' '.join([str(x) for x in ans[1:]]) + '\n')
main()


from queue import Queue

class Node:

	def __init__(self, idx, d=-1):
		self.d = d
		self.idx = idx
		self.par = []
t = int(input())
for _ in range(t):
	dkk = input()
	(c, eds) = tuple([int(x) for x in input().split()])
	adl = [[] for i in range(c + 1)]
	for z in range(eds):
		(u, v) = tuple([int(x) for x in input().split()])
		adl[u - 1].append(v - 1)
	nodes = [Node(i) for i in range(c)]
	q = Queue()
	q.put(0)
	ans = [10 ** 9] * c
	ans[0] = nodes[0].d = 0

	def rewind(x, dis):
		if ans[x] > dis:
			ans[x] = dis
		else:
			return
		for sdd in nodes[x].par:
			rewind(sdd, dis)
	while q.qsize():
		front = q.get()
		for e in adl[front]:
			if nodes[e].d == -1:
				q.put(e)
				nodes[e].d = nodes[front].d + 1
				nodes[e].par.append(front)
				ans[e] = min(ans[e], nodes[e].d)
			elif nodes[e].d > nodes[front].d:
				nodes[e].par.append(front)
				ans[e] = min(ans[e], nodes[e].d)
			else:
				rewind(front, nodes[e].d)
	for e in ans:
		print(e, end=' ')
	print()


from collections import deque
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u):
	vis[u] = 1
	for j in adj[u]:
		if dist[u] >= dist[j]:
			continue
		if not vis[j]:
			yield dfs(j)
		ans[u] = min(ans[u], ans[j])
	yield
t = int(input())
for i in range(t):
	p = input()
	(n, m) = map(int, input().split())
	adj = [[] for j in range(n + 1)]
	for j in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
	dist = [float('inf')] * (n + 1)
	dist[1] = 0
	q = deque()
	q.append(1)
	vis = [0] * (n + 1)
	vis[1] = 1
	while q:
		u = q.popleft()
		for j in adj[u]:
			if not vis[j]:
				dist[j] = 1 + dist[u]
				vis[j] = 1
				q.append(j)
	ans = [float('inf')] * (n + 1)
	for j in range(1, n + 1):
		vis[j] = 0
		ans[j] = dist[j]
		for v in adj[j]:
			ans[j] = min(ans[j], dist[v])
	for i in range(1, n + 1):
		if not vis[i]:
			dfs(i)
	ans.pop(0)
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def MI1():
	return map(int1, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
from collections import deque
for _ in range(II()):
	SI()
	(n, m) = MI()
	to = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = MI1()
		to[u].append(v)
	dd = [inf] * n
	dd[0] = 0
	q = deque()
	q.append((0, 0))
	while q:
		(u, d) = q.popleft()
		for v in to[u]:
			if dd[v] != inf:
				continue
			dd[v] = d + 1
			q.append((v, d + 1))
	ans = [inf] * n
	for u in range(n):
		if to[u]:
			ans[u] = min((dd[v] for v in to[u]))
		ans[u] = min(ans[u], dd[u])
	topo = []
	fin = [False] * n

	def topo_sort(u):
		stack = [u]
		while stack:
			u = stack.pop()
			if fin[u]:
				topo.append(u)
			else:
				fin[u] = True
				stack.append(u)
				for v in to[u]:
					if dd[v] <= dd[u]:
						continue
					if fin[v]:
						continue
					stack.append(v)
	for u in range(n):
		if fin[u]:
			continue
		topo_sort(u)
	for u in topo:
		for v in to[u]:
			if dd[v] <= dd[u]:
				continue
			ans[u] = min(ans[u], ans[v])
	print(*ans)


import sys
from collections import defaultdict, deque
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	link = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		link[u - 1].append(v - 1)
	d = [0] + [-1] * (n - 1)
	ans = [0] + [float('inf')] * (n - 1)
	q = deque([(0, 0)])
	l = []
	while q:
		(step, u) = q.popleft()
		l.append(u)
		for v in link[u]:
			if d[v] == -1:
				d[v] = step + 1
				ans[v] = step + 1
				q.append((step + 1, v))
	for u in range(1, n):
		for v in link[u]:
			ans[u] = min(d[v], ans[u])
	for u in l[::-1]:
		for v in link[u]:
			if d[v] > d[u]:
				ans[u] = min(ans[u], ans[v])
	print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
for _ in range(int(input())):
	_ = input()
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a].append(b)
	A = []
	d = [0] + [-1] * (n - 1)
	q = deque([(0, 0)])
	ans = [float('inf')] * n
	ans[0] = 0
	while q:
		(step, i) = q.popleft()
		A.append(i)
		for j in G[i]:
			if d[j] == -1:
				d[j] = step + 1
				ans[j] = step + 1
				q.append((step + 1, j))
	for i in range(n):
		for j in G[i]:
			ans[i] = min(ans[i], d[j])
	for i in A[::-1]:
		for j in G[i]:
			if d[j] > d[i]:
				ans[i] = min(ans[i], ans[j])
	print(*ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

@iterative
def dfs(v, visited, st, dis, ans):
	visited[st] = 1
	for i in v[st]:
		if visited[i] == 0 and dis[i] > dis[st]:
			ok = (yield dfs(v, visited, i, dis, ans))
		if dis[i] > dis[st]:
			ans[st] = min(ans[st], ans[i])
		else:
			ans[st] = min(ans[st], dis[i])
	yield True

def bfs(g, st):
	visited = [-1] * len(g)
	visited[st] = 0
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if visited[i] == -1:
				visited[i] = visited[s] + 1
				queue.append(i)
	return visited

def solve(case):
	inp()
	(n, m) = sep()
	g = [[] for i in range(n)]
	store = []
	for i in range(m):
		(u, v) = sep()
		u -= 1
		v -= 1
		store.append((u, v))
		g[u].append(v)
	vis = [0] * n
	dis = bfs(g, 0)
	vis = [0] * n
	ans = deepcopy(dis)
	dfs(g, vis, 0, dis, ans)
	print(' '.join((str(ans[i]) for i in range(n))))
testcase(int(inp()))


import heapq
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	graph1 = [[] for _ in range(n + 1)]
	graph2 = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph1[u].append(v)
		graph2[v].append(u)
	d = [999999] * (n + 1)
	q = []
	heapq.heappush(q, (0, 1))
	d[1] = 0
	while q:
		(dist, now) = heapq.heappop(q)
		if d[now] < dist:
			continue
		for i in graph1[now]:
			if dist + 1 < d[i]:
				d[i] = dist + 1
				heapq.heappush(q, (dist + 1, i))
	result = [int(1000000000.0)] * (n + 1)
	q = []
	for i in range(1, n + 1):
		heapq.heappush(q, (d[i], i, True))
	while q:
		(dv, v, flag) = heapq.heappop(q)
		if result[v] == int(1000000000.0):
			result[v] = dv
		for i in graph2[v]:
			if d[v] > d[i]:
				if dv < result[i]:
					heapq.heappush(q, (dv, i, flag))
			elif flag:
				if dv < result[i]:
					heapq.heappush(q, (dv, i, False))
	print(*result[1:], sep=' ')


import os, sys
from io import BytesIO, IOBase
from collections import deque
from heapq import *

def short(n, path):
	visi = [1] + [0] * (n - 1)
	dist = [0] + [10 ** 20] * (n - 1)
	curr = deque([0])
	while len(curr):
		x = curr.popleft()
		for i in path[x]:
			if visi[i]:
				continue
			visi[i] = 1
			dist[i] = dist[x] + 1
			curr.append(i)
	return dist

def algo(n, path, ans, val):
	he = [(val[i], 0, i) for i in range(n)]
	heapify(he)
	visi = [[0, 0] for _ in range(n)]
	while len(he):
		(z, y, x) = heappop(he)
		if visi[x][y]:
			continue
		visi[x][y] = 1
		ans[x][y] = min(ans[x][y], z)
		for i in path[x]:
			if val[i] < val[x]:
				heappush(he, (z, y, i))
			elif not y:
				heappush(he, (z, 1, i))

def main():
	for _ in range(int(input())):
		input()
		(n, m) = map(int, input().split())
		path = [[] for _ in range(n)]
		path1 = [[] for _ in range(n)]
		for _ in range(m):
			(u1, v1) = map(int, input().split())
			path[u1 - 1].append(v1 - 1)
			path1[v1 - 1].append(u1 - 1)
		val = short(n, path)
		ans = [[val[i], val[i]] for i in range(n)]
		algo(n, path1, ans, val)
		for i in ans:
			print(min(i), end=' ')
		print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import deque
T = int(input())
for case in range(T):
	a = input()
	(n, m) = map(int, input().split())
	G = [[] for ele in range(n + 1)]
	d = [-1] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		G[x].append(y)
	q = deque()
	q.append(1)
	d[1] = 0
	count = 0
	while q:
		count += 1
		for i in range(len(q)):
			node = q.popleft()
			for ele in G[node]:
				if d[ele] == -1:
					d[ele] = count
					q.append(ele)
	ans = [0] * (n + 1)
	for u in sorted([i + 1 for i in range(n)], key=lambda x: d[x], reverse=True):
		ans[u] = d[u]
		for v in G[u]:
			if d[u] >= d[v]:
				ans[u] = min(ans[u], d[v])
			else:
				ans[u] = min(ans[u], ans[v])
	print(*ans[1:])