Given a Directed Acyclic Graph having V vertices and E edges, where each edge {U, V} represents the Jobs U and V such that Job V can only be started only after completion of Job U. The task is to determine the minimum time taken by each job to be completed where each Job takes unit time to get completed.
Example 1:
Input:
N=10
M=13
edges[]={{1,3},{1,4},{1,5},{2,3},{2,8},{2,9},{3,6},{4,6},{4,8},{5,8},{6,7},{7,8},{8,10}}
Output:
time[]={1,1,2,2,2,3,4,5,2,6 }
Explanation:
Start jobs 1 and 2 at the beginning and complete them at 1 unit of time. 
Since, all the jobs on which need to be completed before the jobs 3, 4, 5, and 9 are completed. So, we can start these jobs at 1st unit of time and complete these at 2nd unit of time after the completion of the dependent Job.
Similarly, 
Job 6 can only be done after the 3rd and 4th jobs are done. So, start it at the 2nd unit of time and complete it at the 3rd unit of time.
Job 7 can only be done after job 6 is done. So, you can start it at the 3rd unit of time and complete it at the 4th unit of time.
Job 8 can only be done after the 4th, 5th, and 7th jobs are done. So, start it at the 4th unit of time and complete it at the 5th unit of time.
Job 10 can only be done after the 8th job is done. So, start it at the 5th unit of time and complete it at the 6th unit of time.
Example2:
Input:
N=7
M=7
edges[]={{1,2},{2,3},{2,4},{2,5},{3,6},{4,6},{5,7}}
Output:
time[]={1,2,3,3,3,4,4}
Explanation:
Start Job 1 at the beginning and complete it at 1st unit of time.
Job 2 can only be done after 1st Job is done. So, start it at 1st unit of time and complete it at 2nd unit of time.
Since, Job 3, 4, and 5 have the only dependency on the 2nd Job. So, start these jobs at the 2nd unit of time and complete these at the 3rd unit of time.
Job 6 can only be done after the 3rd and 4th Job is done. So, start it at the 3rd unit of time and complete it at the 4th unit of time.
Job 7 can only be done after the 5th Job is done. So, start it at the 3rd hour and complete it at the 4th unit of time.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimumTime() which takes the edge list e[] of the graph, its size number of nodes N and M the number of edges as input parameters and returns the time array.
 
Expected Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges. 
Expected Auxiliary Space: O(V)
 
Constraints:
1 <= N <= 10^{3}
1<=M<=N*(N-1)/2
1<=edges[i][0],edges[i][1]<=N.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





from typing import List





class Solution:

    def minimumTime(self, n : int,m : int, edges : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		incoming = [0] * (n + 1)
		for (x, y) in edges:
			graph[x].append(y)
			incoming[y] += 1
		queue = deque()
		for (idx, val) in enumerate(incoming):
			if idx != 0 and val == 0:
				queue.append(idx)
		ans = [0] * (n + 1)
		count = 1
		while queue:
			size = len(queue)
			for _ in range(size):
				node = queue.popleft()
				ans[node] = str(count)
				for ver in graph[node]:
					incoming[ver] -= 1
					if incoming[ver] == 0:
						queue.append(ver)
			count += 1
		return ' '.join(ans[1:])


from typing import List
from collections import deque, defaultdict
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		Indegree = defaultdict(int)
		visited = set([i for i in range(1, n + 1)])
		for (a, b) in edges:
			graph[a].append(b)
			Indegree[b] += 1
			if b in visited:
				visited.remove(b)
		queue = deque(list(visited))
		answer = [1 for i in range(n)]
		time = 0
		while queue:
			time += 1
			for _ in range(len(queue)):
				cur = queue.popleft()
				answer[cur - 1] = str(time)
				for child in graph[cur]:
					Indegree[child] -= 1
					if Indegree[child] == 0 and child not in visited:
						visited.add(child)
						queue.append(child)
		return ' '.join(answer)


from typing import List
from typing import List
from collections import defaultdict
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		dic = defaultdict(list)
		incoming = defaultdict(int)
		for (u, v) in edges:
			dic[u].append(v)
			incoming[v] += 1
		queue = deque()
		visited = set()
		for key in dic:
			if incoming[key] == 0:
				queue.append(key)
				visited.add(key)
		path = [str(1)] * n
		level = 1
		while queue:
			level += 1
			length = len(queue)
			for i in range(length):
				node = queue.popleft()
				for child in dic[node]:
					if child not in visited:
						if incoming[child] == 1:
							path[child - 1] = str(level)
							queue.append(child)
							visited.add(child)
						else:
							incoming[child] -= 1
		return ' '.join(path)


from typing import List
from typing import List
from collections import *

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indeg = defaultdict(int)
		for i in range(n):
			indeg[i + 1] = 0
		for (u, v) in edges:
			graph[u].append(v)
			indeg[v] += 1
		qu = deque()
		for (key, val) in indeg.items():
			if val == 0:
				qu.append([key, 1])
		times = [0] * n
		while qu:
			(node, time) = qu.popleft()
			times[node - 1] = time
			for nbr in graph[node]:
				indeg[nbr] -= 1
				if indeg[nbr] == 0:
					qu.append([nbr, time + 1])
		return ' '.join(map(str, times))


from typing import List
from typing import List
from collections import defaultdict
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indeg = defaultdict(int)
		for (indep, dep) in edges:
			graph[indep].append(dep)
			indeg[dep] += 1
		queue = deque()
		visited = set()
		time = [0] * n
		for node in range(n):
			if not indeg[node + 1]:
				queue.append(node + 1)
		count = 1
		while queue:
			for _ in range(len(queue)):
				node = queue.popleft()
				visited.add(node)
				time[node - 1] = count
				for job in graph[node]:
					indeg[job] -= 1
					if not indeg[job] and job not in visited:
						queue.append(job)
			count += 1
		return ' '.join(map(str, time[:]))


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		import collections
		seen = [0] * n
		incoming = [0] * n
		graph = {idx: [] for idx in range(n)}
		for (fro_m, to) in edges:
			incoming[to - 1] += 1
			graph[fro_m - 1].append(to - 1)
		queue = collections.deque()
		for idx in range(n):
			if incoming[idx] == 0:
				queue.append(idx)
		time = 1
		answer = [0] * n
		while queue:
			size = len(queue)
			for i in range(size):
				node = queue.popleft()
				answer[node] = time
				for adj in graph[node]:
					incoming[adj] -= 1
					if incoming[adj] == 0:
						queue.append(adj)
			time += 1
		ans = ''
		for ind in range(n):
			if ind != n - 1:
				ans += str(answer[ind]) + ' '
			else:
				ans += str(answer[ind])
		return ans


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		depend = defaultdict(int)
		adj = defaultdict(list)
		ans = [0] * n
		seen = set()
		time = 1
		for edge in edges:
			adj[edge[0]].append(edge[1])
			adj[edge[1]].append(edge[0])
			depend[edge[1]] += 1
		q = deque()
		for val in range(1, n + 1):
			if depend[val] == 0:
				q.append(val)
				ans[val - 1] = str(time)
		count = 0
		while q:
			if count == 0:
				time += 1
				count = len(q)
			val = q.popleft()
			count -= 1
			seen.add(val)
			for ad in adj[val]:
				depend[ad] -= 1
				if ad not in seen and depend[ad] < 1:
					q.append(ad)
					ans[ad - 1] = str(time)
					seen.add(ad)
		return ' '.join(ans)


from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		time = [0] * n
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for (fr, to) in edges:
			graph[fr].append(to)
			indegree[to] += 1
		visited = set()
		queue = deque()
		for i in range(n):
			if not indegree[i + 1]:
				visited.add(i + 1)
				queue.append(i + 1)
		time_elapsed = 1
		while queue:
			length = len(queue)
			for _ in range(length):
				curr = queue.popleft()
				time[curr - 1] = time_elapsed
				for n in graph[curr]:
					indegree[n] -= 1
					if indegree[n] < 1:
						queue.append(n)
			time_elapsed += 1
		time = list(map(str, time))
		return ' '.join(time)


from typing import List
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = [[] for i in range(n)]
		incoming = [0 for i in range(n)]
		ans = [1 for i in range(n)]
		for (a, b) in edges:
			(a, b) = (a - 1, b - 1)
			graph[a].append(b)
			incoming[b] += 1
		q = deque()
		for i in range(n):
			if incoming[i] == 0:
				q.append(i)
		while q:
			vertex = q.popleft()
			for adjvertex in graph[vertex]:
				incoming[adjvertex] -= 1
				ans[adjvertex] = max(ans[adjvertex], ans[vertex] + 1)
				if incoming[adjvertex] == 0:
					q.append(adjvertex)
		ans = list(map(str, ans))
		return ' '.join(ans)


from typing import List
from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		incoming = defaultdict(int)
		graph = defaultdict(list)
		for (start, end) in edges:
			graph[start].append(end)
			incoming[end] += 1
		task_queue = deque()
		minimum_time = defaultdict(int)
		level = 1
		for key in range(1, n + 1):
			if incoming[key] == 0:
				task_queue.append(key)
		while task_queue:
			len_level = len(task_queue)
			for _ in range(len_level):
				task = task_queue.popleft()
				minimum_time[task] = str(level)
				for related_task in graph[task]:
					incoming[related_task] -= 1
					if incoming[related_task] == 0:
						task_queue.append(related_task)
			level += 1
		ans = list(minimum_time.values())
		return ' '.join(ans)


from typing import List
from typing import List
import collections

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = collections.defaultdict(list)
		pre_count = [0] * (n + 1)
		for (parent, child) in edges:
			graph[parent].append(child)
			pre_count[child] += 1
		que = collections.deque([])
		for job in range(1, n + 1):
			if pre_count[job] == 0:
				que.append((job, 1))
		minimum_time = ['0'] * n
		while que:
			(job, time) = que.popleft()
			minimum_time[job - 1] = str(time)
			for sequel in graph[job]:
				pre_count[sequel] -= 1
				if pre_count[sequel] == 0:
					que.append((sequel, time + 1))
		return ' '.join(minimum_time)


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indeg = [0] * (n + 1)
		graph = defaultdict(list)
		ans = [0] * (n + 1)
		for (val1, val2) in edges:
			graph[val1].append(val2)
			indeg[val2] += 1
		time = 1
		queue = deque()
		for (i, val) in enumerate(indeg):
			if val == 0 and i != 0:
				queue.append(i)
		while queue:
			length = len(queue)
			for _ in range(length):
				node = queue.popleft()
				ans[node] = str(time)
				for val in graph[node]:
					indeg[val] -= 1
					if indeg[val] == 0:
						queue.append(val)
			time += 1
		return ' '.join(ans[1:])


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indegree = [0] * (n + 1)
		for (fr, to) in edges:
			graph[fr].append(to)
			indegree[to] += 1
		queue = deque()
		for i in range(1, n + 1):
			if indegree[i] == 0:
				queue.append(i)
		ans = [0] * (n + 1)
		time = 1
		while queue:
			l = len(queue)
			for _ in range(l):
				curr = queue.popleft()
				ans[curr] = time
				for nbr in graph[curr]:
					indegree[nbr] -= 1
					if indegree[nbr] == 0:
						queue.append(nbr)
			time += 1
		return ' '.join(map(str, ans[1:]))


from typing import List
from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ans = [0 for _ in range(n)]
		d = defaultdict(list)
		length = defaultdict(int)
		for (x, y) in edges:
			d[x].append(y)
			length[y] += 1
		queue = deque()
		for i in range(1, n + 1):
			if length[i] == 0:
				queue.append(i)
		while queue:
			num = queue.popleft()
			ans[num - 1] += 1
			for i in d[num]:
				ans[i - 1] = max(ans[i - 1], ans[num - 1])
				length[i] -= 1
				if length[i] == 0:
					queue.append(i)
		return ' '.join([str(v) for v in ans])


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ans = [0] * n
		mp = defaultdict(list)
		deg = defaultdict(int)
		for (start, end) in edges:
			mp[start - 1].append(end - 1)
			deg[end - 1] += 1
		q = deque()
		for i in range(n):
			if not deg[i]:
				q.append(i)
				ans[i] = 1
		while q:
			poped = q.popleft()
			for neighbor in mp[poped]:
				deg[neighbor] -= 1
				if not deg[neighbor]:
					q.append(neighbor)
				ans[neighbor] = max(ans[neighbor], ans[poped] + 1)
		return ' '.join(map(str, ans))


from typing import List
from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		incoming = [0] * n
		result = [0] * n
		for (start, end) in edges:
			graph[start].append(end)
			incoming[end - 1] += 1
		queue = deque()
		for (key, val) in enumerate(incoming):
			if val == 0:
				queue.append(key + 1)
		count = 1
		while queue:
			size = len(queue)
			for i in range(size):
				popped = queue.popleft()
				result[popped - 1] = str(count)
				for nbr in graph[popped]:
					incoming[nbr - 1] -= 1
					if incoming[nbr - 1] == 0:
						queue.append(nbr)
			count += 1
		return ' '.join(result)


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj_list = defaultdict(list)
		time = [0] * n
		in_degree = [0] * n
		quee = deque()
		for (first, second) in edges:
			adj_list[first - 1].append(second - 1)
			in_degree[second - 1] += 1
		for i in range(len(in_degree)):
			if in_degree[i] == 0:
				quee.append((i, 1))
		while quee:
			val = quee.popleft()
			time[val[0]] = val[1]
			for nebor in adj_list[val[0]]:
				in_degree[nebor] -= 1
				if in_degree[nebor] == 0:
					quee.append((nebor, val[1] + 1))
		return ' '.join(map(str, time))


from typing import List
from typing import List
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		visited = set()
		indegree = defaultdict(int)
		for (start, end) in edges:
			graph[start].append(end)
			indegree[end] += 1
		level = []
		for i in range(1, n + 1):
			if not indegree[i]:
				level.append(i)
		res = [0] * n
		i = 0
		while level:
			nxt = []
			i += 1
			for num in level:
				visited.add(num)
				res[num - 1] = i
				for neigh in graph[num]:
					indegree[neigh] -= 1
					if indegree[neigh] == 0 and neigh not in visited:
						nxt.append(neigh)
			level = nxt
		return ' '.join((str(r) for r in res))


from typing import List
from collections import defaultdict
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		time = [0] * n
		graph = defaultdict(list)
		queue = deque()
		incoming = defaultdict(int)
		for (pre, task) in edges:
			graph[pre].append(task)
			incoming[task] += 1
		for i in range(1, n + 1):
			if incoming[i] == 0:
				queue.append(i)
				time[i - 1] = 1
		level = 1
		while queue:
			for i in range(len(queue)):
				item = queue.popleft()
				for i in graph[item]:
					incoming[i] -= 1
					if incoming[i] == 0:
						time[i - 1] = level + 1
						queue.append(i)
			level += 1
		for i in range(len(time)):
			time[i] = str(time[i])
		return ' '.join(time)


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		from collections import defaultdict
		graph = defaultdict(list)
		indegree = [0 for i in range(n)]
		for (frm, to) in edges:
			graph[frm].append(to)
			indegree[to - 1] += 1
		init_nodes = [(i + 1, 1) for i in range(len(indegree)) if indegree[i] == 0]
		ans = [1 if indegree[i] == 0 else 0 for i in range(n)]

		def bfs(nodes):
			from collections import deque
			queue = deque(nodes)
			while queue:
				(node, step) = queue.popleft()
				for neighbour in graph[node]:
					indegree[neighbour - 1] -= 1
					if not indegree[neighbour - 1]:
						ans[neighbour - 1] = step + 1
						queue.append((neighbour, step + 1))
			return ' '.join(map(str, ans))
		return bfs(init_nodes)


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		temp = defaultdict(int)
		graph = defaultdict(set)
		e = defaultdict(int)
		for (f, t) in edges:
			graph[f].add(t)
			e[t] += 1
		que = deque()
		for i in range(1, n + 1):
			if e[i] == 0:
				que.append(i)
		counter = 1
		while que:
			level = len(que)
			for _ in range(level):
				node = que.popleft()
				temp[node] = counter
				for i in graph[node]:
					e[i] -= 1
					if e[i] == 0:
						que.append(i)
			counter += 1
		result = [str(temp[i]) for i in range(1, n + 1)]
		result = ' '.join(result)
		return result


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = defaultdict(int)
		adjList = defaultdict(list)
		for (from_, to_) in edges:
			adjList[from_].append(to_)
			indegree[to_] += 1
		queue = deque()
		for node in range(1, n + 1):
			if indegree[node] == 0:
				queue.append(node)
		answer = [0 for _ in range(n)]
		layer = 1
		while queue:
			for _ in range(len(queue)):
				curr = queue.popleft()
				answer[curr - 1] = layer
				for neighbor in adjList[curr]:
					indegree[neighbor] -= 1
					if indegree[neighbor] == 0:
						queue.append(neighbor)
			layer += 1
		return ' '.join(list(map(str, answer)))


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = [[] for _ in range(n)]
		indegree = [0 for _ in range(n)]
		for (u, v) in edges:
			graph[u - 1].append(v - 1)
			indegree[v - 1] += 1
		q = deque()
		for node in range(n):
			if indegree[node] == 0:
				q.append((node, 1))
		time = [-1 for _ in range(n)]
		while q:
			(node, curr_time) = q.popleft()
			time[node] = curr_time
			for child in graph[node]:
				indegree[child] -= 1
				if indegree[child] == 0:
					q.append((child, curr_time + 1))
		return ' '.join((str(t) for t in time))


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = [[] for _ in range(n)]
		indegree = [0 for _ in range(n)]
		for (a, b) in edges:
			graph[a - 1].append(b - 1)
			indegree[b - 1] += 1
		queue = deque()
		for i in range(n):
			if indegree[i] == 0:
				queue.append((i, 1))
		minCompletion = [0 for _ in range(n)]
		while queue:
			(val, time) = queue.popleft()
			minCompletion[val] = time
			for neighbour in graph[val]:
				indegree[neighbour] -= 1
				if indegree[neighbour] == 0:
					queue.append((neighbour, time + 1))
		return ' '.join((str(val) for val in minCompletion))


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indegree = [0] * (n + 1)
		for (u, v) in edges:
			graph[u].append(v)
			indegree[v] += 1
		queue = deque()
		for i in range(1, n + 1):
			if indegree[i] == 0:
				queue.append(i)
		time = ['0'] * n
		level = 1
		while queue:
			size = len(queue)
			for _ in range(size):
				curr = queue.popleft()
				time[curr - 1] = str(level)
				for neighbour in graph[curr]:
					indegree[neighbour] -= 1
					if indegree[neighbour] == 0:
						queue.append(neighbour)
			level += 1
		return ' '.join(time)


from typing import List
from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		degree = [0] * (n + 1)
		ans = [0] * (n + 1)
		for (From, to) in edges:
			graph[From].append(to)
			degree[to] += 1
		que = deque()
		for i in range(n + 1):
			if degree[i] == 0:
				que.append(i)
				ans[i] = 1
		que.popleft()
		while que:
			curNode = que.popleft()
			for node in graph[curNode]:
				degree[node] -= 1
				if degree[node] == 0:
					nextTime = ans[curNode] + 1
					ans[node] = nextTime
					que.append(node)
		ans = [str(x) for x in ans]
		return ' '.join(ans[1:])


from typing import List
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		GRAPH = defaultdict(list)
		time = [0] * n
		for (adj, node) in edges:
			GRAPH[node - 1].append(adj - 1)

		def dfs(node):
			if time[node]:
				return time[node]
			ans = 0
			for adj in GRAPH[node]:
				ans = max(ans, dfs(adj))
			time[node] = ans + 1
			return time[node]
		for node in range(n):
			dfs(node)
		return ' '.join(map(str, time))


from typing import List
from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		incomings = defaultdict(int)
		for (u, v) in edges:
			graph[u].append(v)
			incomings[v] += 1
		queue = deque()
		for job in range(1, n + 1):
			if incomings[job] == 0:
				queue.append(job)
		level = 0
		time = [0] * n
		while queue:
			level += 1
			length = len(queue)
			for _ in range(length):
				curr = queue.popleft()
				time[curr - 1] = level
				for next in graph[curr]:
					incomings[next] -= 1
					if incomings[next] == 0:
						queue.append(next)
		return ' '.join(map(str, time))


from typing import List
from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indegree = defaultdict(int)
		time = [0 for _ in range(n)]
		for (source, des) in edges:
			graph[source - 1].append(des - 1)
			indegree[des - 1] += 1
		queue = deque()
		for i in range(n):
			if indegree[i] == 0:
				queue.append(i)
		levelCount = 0
		while queue:
			levelCount += 1
			length = len(queue)
			for _ in range(length):
				node = queue.popleft()
				time[node] = str(levelCount)
				for neighbor in graph[node]:
					indegree[neighbor] -= 1
					if indegree[neighbor] == 0:
						queue.append(neighbor)
		return ' '.join(time)


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ans = [str(0)] * n
		adjList = defaultdict(list)
		indegree = [0] * n
		queue = deque()
		for (u, v) in edges:
			adjList[u - 1].append(v - 1)
			indegree[v - 1] += 1
		for i in range(n):
			if indegree[i] == 0:
				queue.append(i)
		time = 1
		while queue:
			for _ in range(len(queue)):
				node = queue.popleft()
				ans[node] = str(time)
				for dep in adjList[node]:
					indegree[dep] -= 1
					if indegree[dep] == 0:
						queue.append(dep)
			time += 1
		return ' '.join(ans)


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		afterComes = defaultdict(list)
		preReq = [0] * n
		for (U, V) in edges:
			afterComes[U - 1].append(V - 1)
			preReq[V - 1] += 1
		que = deque()
		finished = set()
		for i in range(n):
			if preReq[i] == 0:
				que.append(i)
				finished.add(i)
		timeTaken = [0] * n
		time = 1
		while que:
			for _ in range(len(que)):
				job = que.popleft()
				timeTaken[job] = str(time)
				for after in afterComes[job]:
					preReq[after] -= 1
					if preReq[after] == 0:
						que.append(after)
			time += 1
		return ' '.join(timeTaken)


from typing import List
from typing import List
import collections

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = collections.defaultdict(list)
		indegree = [0] * (n + 1)
		for (u, v) in edges:
			graph[u].append(v)
			indegree[v] += 1
		q = collections.deque()
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
		ans = []
		lev = 1
		ans = [0] * n
		while q:
			q_len = len(q)
			for _ in range(q_len):
				top = q.popleft()
				ans[top - 1] = lev
				for adj in graph[top]:
					indegree[adj] -= 1
					if indegree[adj] == 0:
						q.append(adj)
			lev += 1
		return ' '.join(map(str, ans))


from typing import List
from typing import List
from collections import deque, defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		incoming = defaultdict(int)
		for (u, v) in edges:
			graph[u].append(v)
			incoming[v] += 1
		queue = deque()
		for i in range(1, n + 1):
			if incoming[i] == 0:
				queue.append((i, 1))
		answer = [0] * n
		while queue:
			for _ in range(len(queue)):
				(node, level) = queue.popleft()
				answer[node - 1] = str(level)
				for neighbour in graph[node]:
					incoming[neighbour] -= 1
					if incoming[neighbour] == 0:
						queue.append((neighbour, level + 1))
		return ' '.join(answer)


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ans = ['0'] * n
		graph = defaultdict(list)
		degree = defaultdict(int)
		for (src, end) in edges:
			graph[src - 1].append(end - 1)
			degree[end - 1] += 1
		queue = deque()
		for index in range(n):
			if degree[index] == 0:
				queue.append(index)
		while queue:
			curr = queue.popleft()
			ans[curr] = str(int(ans[curr]) + 1)
			for child in graph[curr]:
				degree[child] -= 1
				ans[child] = str(max(int(ans[curr]), int(ans[child])))
				if degree[child] == 0:
					queue.append(child)
		return ' '.join(ans)


from typing import List
from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = defaultdict(int)
		graph = defaultdict(list)
		for (free, depend) in edges:
			graph[free].append(depend)
			indegree[depend] += 1
		queue = deque()
		for idx in range(1, n + 1):
			if indegree[idx] == 0:
				queue.append(idx)
		result = [0] * n
		time = 1
		while queue:
			l = len(queue)
			for _ in range(l):
				curr = queue.popleft()
				result[curr - 1] = str(time)
				for neigh in graph[curr]:
					indegree[neigh] -= 1
					if indegree[neigh] == 0:
						queue.append(neigh)
			time += 1
		return ' '.join(result)


from typing import List
from collections import deque, defaultdict
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = [0 for _ in range(n + 1)]
		graph = defaultdict(list)
		times = [0 for _ in range(n)]
		for edge in edges:
			graph[edge[0]].append(edge[1])
			indegree[edge[1]] += 1
		Q = deque()
		for i in range(1, n + 1):
			if indegree[i] == 0:
				Q.append((i, 1))
		while Q:
			(current, t) = Q.popleft()
			times[current - 1] = str(t)
			for adj in graph[current]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					Q.append((adj, t + 1))
		return ' '.join(times)


from typing import List
from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = defaultdict(int)
		outdegree = defaultdict(list)
		queue = deque()
		levels = 1
		time = [0 for i in range(n)]
		for (a, b) in edges:
			indegree[b] += 1
			outdegree[a].append(b)
		for idx in range(1, n + 1):
			if not indegree[idx]:
				queue.append(idx)
				time[idx - 1] = str(1)
		while queue:
			N = len(queue)
			for _ in range(N):
				cur = queue.popleft()
				for elm in outdegree[cur]:
					indegree[elm] -= 1
					if indegree[elm] == 0:
						queue.append(elm)
						time[elm - 1] = str(levels + 1)
			levels += 1
		return ' '.join(time)


from typing import List
from collections import *
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indeg = [0] * n
		graph = defaultdict(list)
		res = [0] * n
		for (a, b) in edges:
			graph[a].append(b)
			indeg[b - 1] += 1
		queue = deque()
		for i in range(n):
			if indeg[i] == 0:
				queue.append((i + 1, 1))
		while queue:
			node = queue.popleft()
			res[node[0] - 1] = node[1]
			for neigh in graph[node[0]]:
				indeg[neigh - 1] -= 1
				if indeg[neigh - 1] == 0:
					queue.append((neigh, node[1] + 1))
		return ' '.join(map(str, res))


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]):
		indegree = [0] * n
		adj_list = defaultdict(list)
		to_do = deque()
		result = [-1] * n
		visited = set()
		for (src, dst) in edges:
			adj_list[src - 1].append(dst - 1)
			indegree[dst - 1] += 1
		for i in range(n):
			if indegree[i] == 0:
				to_do.append((i, 1))
		while to_do:
			(curr, dis) = to_do.popleft()
			if result[curr] == -1:
				result[curr] = dis
			for child in adj_list[curr]:
				indegree[child] -= 1
				if indegree[child] == 0:
					to_do.append((child, dis + 1))
		return ' '.join(map(str, result))


from typing import List
from collections import deque, defaultdict
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ans = [1] * n
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for (start, end) in edges:
			graph[start].append(end)
			indegree[end] += 1
		queue = deque()
		for i in range(1, n + 1):
			if i not in indegree:
				queue.append(i)
		time = 1
		while queue:
			size = len(queue)
			for _ in range(size):
				vertix = queue.popleft()
				ans[vertix - 1] = str(time)
				for val in graph[vertix]:
					indegree[val] -= 1
					if indegree[val] == 0:
						queue.append(val)
			time += 1
		return ' '.join(ans)


from typing import List
from collections import defaultdict
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indegree = defaultdict(int)
		for (node1, node2) in edges:
			graph[node1].append(node2)
			indegree[node2] += 1
		queue = deque([])
		for i in range(1, n + 1):
			if indegree[i] == 0:
				queue.append((i, 1))
		min_time = [0] * n
		while queue:
			(jop, time) = queue.popleft()
			min_time[jop - 1] = str(time)
			for neighbour in graph[jop]:
				indegree[neighbour] -= 1
				if indegree[neighbour] == 0:
					queue.append((neighbour, time + 1))
		return ' '.join(min_time)


from typing import List
from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		prerequisite = {}
		graph = {}
		for (pre, job) in edges:
			if job not in prerequisite:
				prerequisite[job] = 1
			else:
				prerequisite[job] += 1
			if pre not in graph:
				graph[pre] = [job]
			else:
				graph[pre].append(job)
		starters = []
		for i in range(1, n + 1):
			if i not in prerequisite:
				starters.append((i, 1))
		jobs = deque(starters)
		finArr = [1 for i in range(n)]
		while jobs:
			(curJob, level) = jobs.popleft()
			finArr[curJob - 1] = level
			if curJob in graph:
				for consecJobs in graph[curJob]:
					prerequisite[consecJobs] -= 1
					if prerequisite[consecJobs] == 0:
						jobs.append((consecJobs, level + 1))
		return ' '.join(list(map(str, finArr)))


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		dic = defaultdict(list)
		incoming = [1] * n
		for (u, v) in edges:
			dic[u].append(v)
			incoming[v - 1] += 1
		visited = set()
		queue = deque()
		for i in range(n):
			if incoming[i] == 1:
				queue.append(i + 1)
				visited.add(i + 1)
		ans = [0] * n
		count = 0
		while queue:
			count += 1
			for i in range(len(queue)):
				x = queue.popleft()
				ans[x - 1] += count
				for j in dic[x]:
					incoming[j - 1] -= 1
					if incoming[j - 1] == 1:
						queue.append(j)
						visited.add(j)
		return ' '.join(list(map(str, ans)))


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		count = defaultdict(int)
		for (u, v) in edges:
			graph[u].append(v)
			count[v] += 1
		queue = deque()
		for i in range(1, n + 1):
			if count[i] == 0:
				queue.append(i)
		result = [0] * n
		time = 1
		while queue:
			l = len(queue)
			for _ in range(l):
				curr = queue.popleft()
				result[curr - 1] = str(time)
				for neigh in graph[curr]:
					count[neigh] -= 1
					if count[neigh] == 0:
						queue.append(neigh)
			time += 1
		return ' '.join(result)


from typing import List
from collections import defaultdict, deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		self.tot_time = [0] * n
		pre_req = [0] * n
		graph = defaultdict(list)
		for (pre, post) in edges:
			graph[post - 1].append(pre - 1)
			pre_req[post - 1] += 1
		self.visited = set()

		def dfs(root):
			self.visited.add(root)
			ans = 0
			for i in graph[root]:
				if i not in self.visited:
					ans = max(ans, dfs(i))
				else:
					ans = max(ans, self.tot_time[i])
			self.tot_time[root] = ans + 1
			return ans + 1
		for i in range(n):
			if i not in self.visited:
				dfs(i)
		answ = []
		return ' '.join(list(map(str, self.tot_time)))


from typing import List
from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		degree = [0 for _ in range(n)]
		answer = [0 for _ in range(n)]
		queue = deque()
		for (u, v) in edges:
			graph[u - 1].append(v - 1)
			degree[v - 1] += 1
		for i in range(n):
			if degree[i] == 0:
				queue.append(i)
		time = 1
		while queue:
			size = len(queue)
			for _ in range(size):
				node = queue.popleft()
				answer[node] = str(time)
				for child in graph[node]:
					degree[child] -= 1
					if degree[child] == 0:
						queue.append(child)
			time += 1
		return ' '.join(answer)


from typing import List
from collections import defaultdict
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = {i: [] for i in range(n)}
		for (u, v) in edges:
			graph[u - 1].append(v - 1)
		indeg = [0] * n
		for node in graph:
			for nei in graph[node]:
				indeg[nei] += 1
		q = []
		job = [0] * n
		for i in range(n):
			if indeg[i] == 0:
				job[i] = 1
				q.append(i)
		while q:
			node = q.pop(0)
			for nei in graph[node]:
				indeg[nei] -= 1
				if indeg[nei] == 0:
					job[nei] = job[node] + 1
					q.append(nei)
		return ' '.join([str(i) for i in job])


from typing import List
from collections import defaultdict as dict, deque as dq
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = dict(list)
		indegree = [0 for i in range(n + 1)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			indegree[edge[1]] += 1
		q = dq([])
		finishTimes = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append((i, 1))
		while q:
			(node, time) = q.popleft()
			finishTimes[node] = time
			for neib in adj[node]:
				indegree[neib] -= 1
				if indegree[neib] == 0:
					q.append((neib, time + 1))
		return ' '.join(map(str, finishTimes[1:]))


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n)]
		inflow = [0] * n
		for (i, j) in edges:
			adj[i - 1].append(j - 1)
			inflow[j - 1] += 1
		time = [0] * n
		q = []
		for i in range(n):
			if inflow[i] == 0:
				q.append(i)
				time[i] = 1
		while len(q):
			for i in range(len(q)):
				u = q.pop(0)
				for v in adj[u]:
					inflow[v] -= 1
					if inflow[v] == 0:
						q.append(v)
						time[v] = time[u] + 1
		for i in time:
			print(i, end=' ')
		return ''


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		indegree = [0] * (n + 1)
		for (u, v) in edges:
			adj[u].append(v)
			indegree[v] += 1
		job = [0] * (n + 1)
		visited = [0] * (n + 1)
		q = []
		for i in range(1, n + 1):
			if indegree[i] == 0:
				job[i] = 1
				q.append(i)
		while len(q):
			s = q.pop(0)
			for nei in adj[s]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					q.append(nei)
					job[nei] = job[s] + 1
		for element in job[1:]:
			print(element, end=' ')
		return ''


from typing import List
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for _ in range(n + 1)]
		for ele in edges:
			adj[ele[0]].append(ele[1])
		degree = [0] * (n + 1)
		for i in range(1, n + 1):
			for j in adj[i]:
				degree[j] += 1
		job = [0] * (n + 1)
		q = []
		for i in range(1, n + 1):
			if degree[i] == 0:
				q.append(i)
				job[i] = 1
		while q:
			u = q.pop(0)
			for nbr in adj[u]:
				degree[nbr] -= 1
				if degree[nbr] == 0:
					job[nbr] = 1 + job[u]
					q.append(nbr)
		job.pop(0)
		ans = ''
		for ele in job:
			ans += str(ele)
			ans += ' '
		return ans


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = [[] for i in range(n)]
		for ele in edges:
			graph[ele[0] - 1].append(ele[1])
		degree = [0 for i in range(n)]
		for i in range(n):
			for j in graph[i]:
				degree[j - 1] += 1
		job = [0] * n
		q = []
		for i in range(n):
			if degree[i] == 0:
				q.append(i)
				job[i] = 1
		while q:
			cur = q.pop(0)
			for adj in graph[cur]:
				degree[adj - 1] -= 1
				if degree[adj - 1] == 0:
					job[adj - 1] = 1 + job[cur]
					q.append(adj - 1)
		ans = ''
		for ele in job:
			ans += str(ele)
			ans += ' '
		return ans


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]):
		adj = {c: [] for c in range(n)}
		biAdj = {c: [] for c in range(n)}
		for (dst, src) in edges:
			adj[src - 1].append(dst - 1)
			biAdj[dst - 1].append(src - 1)
		outdegree = [0 for c in range(n)]
		for v in range(n):
			for nei in biAdj[v]:
				outdegree[nei] += 1
		q = deque()
		for i in range(len(outdegree)):
			if outdegree[i] == 0:
				q.append((i, 1))
		timeTaken = [0 for c in range(n)]
		while q:
			length = len(q)
			for i in range(length):
				(job, time) = q.popleft()
				timeTaken[job] = time
				for nei in biAdj[job]:
					outdegree[nei] -= 1
					if outdegree[nei] == 0:
						q.append((nei, time + 1))
		for time in timeTaken[:len(timeTaken) - 1]:
			print(time, end=' ')
		return timeTaken[-1]


from typing import List
from collections import deque
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		incoming = [0] * (n + 1)
		adj = defaultdict(list)
		ans = [-1] * n
		for edge in edges:
			incoming[edge[1]] += 1
			adj[edge[0]].append(edge[1])
		q = deque()
		for i in range(1, n + 1):
			if incoming[i] == 0:
				q.append([i, 1])
		while q:
			top = q.popleft()
			node = top[0]
			time = top[1]
			if ans[node - 1] == -1:
				ans[node - 1] = time
			for ngbhr in adj[node]:
				incoming[ngbhr] -= 1
				if incoming[ngbhr] == 0:
					q.append([ngbhr, time + 1])
		h = ' '
		return h.join(map(str, ans))


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		minTime = [0] * n
		indeg = [0] * n
		for i in edges:
			indeg[i[1] - 1] += 1
		adj = {}
		for i in range(1, n + 1):
			adj[i] = []
		for i in edges:
			adj[i[0]].append(i[1])
		q = []
		for i in range(len(indeg)):
			if indeg[i] == 0:
				minTime[i] = 1
				q.append(i + 1)
		h = ' '
		while q:
			s = q.pop(0)
			for ne in adj[s]:
				indeg[ne - 1] -= 1
				if indeg[ne - 1] == 0:
					minTime[ne - 1] = minTime[s - 1] + 1
					q.append(ne)
		return h.join(map(str, minTime))


from typing import List
from typing import List
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = [0] * (n + 1)
		d = defaultdict(list)
		for i in edges:
			d[i[0]].append(i[1])
		for i in d:
			for nbr in d[i]:
				indegree[nbr] += 1
		q = []
		for i in range(1, len(indegree)):
			if indegree[i] == 0:
				q.append(i)
		ans = [1] * (n + 1)
		while q:
			front = q.pop(0)
			for nbr in d[front]:
				indegree[nbr] -= 1
				if indegree[nbr] == 0:
					ans[nbr] = ans[front] + 1
					q.append(nbr)
		a = ''
		for i in ans[1:]:
			a += str(i)
			a += ' '
		return a


from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		mini = [0 for _ in range(n)]
		adj = [[] for _ in range(n)]
		for (i, j) in edges:
			adj[j - 1].append(i - 1)

		def dfs(i):
			if mini[i] != 0:
				return mini[i]
			if len(adj[i]) == 0:
				mini[i] = 1
			else:
				for j in adj[i]:
					mini[i] = max(mini[i], dfs(j) + 1)
			return mini[i]
		for i in range(n):
			if mini[i] == 0:
				dfs(i)
		return ' '.join(map(str, mini))


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = {}
		degree = [0] * (n + 1)
		degree[0] = -1
		for v in edges:
			graph[v[0]] = [v[1]] + graph.get(v[0], [])
			degree[v[1]] += 1
		q = list()
		for i in range(len(degree)):
			if degree[i] == 0:
				q.append([i, 1])
		ans = list()
		while q:
			cur = q.pop(0)
			ans.append(cur)
			for adj in graph.get(cur[0], []):
				degree[adj] -= 1
				if degree[adj] == 0:
					q.append([adj, cur[1] + 1])
		ans.sort(key=lambda x: x[0])
		ans = [x[1] for x in ans]
		return ' '.join(map(str, ans))


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		n += 1
		adj = []
		ans = [0] * n
		q = deque()
		adj = [[] for _ in range(n)]
		in_degree = [0] * n
		for (s, d) in edges:
			in_degree[d] += 1
			adj[s].append(d)
		for (i, j) in enumerate(in_degree):
			if j == 0:
				q.append((i, 1))
		while q:
			(top, lvl) = q.popleft()
			ans[top] = str(lvl)
			for num in adj[top]:
				in_degree[num] -= 1
				if in_degree[num] == 0:
					q.append((num, lvl + 1))
		return ' '.join(ans[1:])


from collections import deque
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		indeg = [0] * (n + 1)
		t = [0] * (n + 1)
		for (i, j) in edges:
			adj[i].append(j)
			indeg[j] += 1
		q = deque()
		for i in range(1, n + 1):
			if indeg[i] == 0:
				t[i] = 1
				q.append(i)
		while q:
			node = q.popleft()
			for nbr in adj[node]:
				indeg[nbr] -= 1
				if indeg[nbr] == 0:
					t[nbr] = t[node] + 1
					q.append(nbr)
		t.pop(0)
		res = ''
		for i in t:
			res += str(i) + ' '
		return res


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		indegree = [0] * (n + 1)
		ans = ['' for i in range(n)]
		arr = []
		for (i, j) in edges:
			adj[i].append(j)
			indegree[j] += 1
		time = 1
		for i in range(1, n + 1):
			if indegree[i] == 0:
				arr.append(i)
		while arr:
			l = len(arr)
			for i in range(l):
				element = arr.pop(0)
				ans[element - 1] = str(time)
				for j in adj[element]:
					indegree[j] -= 1
					if indegree[j] == 0:
						arr.append(j)
			time += 1
		ans = ' '.join(ans)
		return ans


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		inDegree = [0 for i in range(n + 1)]
		time = 1
		ans = ['' for i in range(n)]
		WeCare = []
		for (x, y) in edges:
			adj[x].append(y)
			inDegree[y] += 1
		for u in range(1, n + 1):
			if inDegree[u] == 0:
				WeCare.append(u)
		while len(WeCare) != 0:
			qlen = len(WeCare)
			for i in range(qlen):
				qele = WeCare.pop(0)
				ans[qele - 1] = str(time)
				for j in adj[qele]:
					inDegree[j] -= 1
					if inDegree[j] == 0:
						WeCare.append(j)
			time += 1
		ans = ' '.join(ans)
		return ans


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		g = [[] for i in range(n + 1)]
		indegree = [0] * (n + 1)
		for (x, y) in edges:
			g[x].append(y)
			indegree[y] += 1
		ans = [0] * (n + 1)
		q = []
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
				ans[i] = 1
		while q:
			val = q.pop(0)
			for nei in g[val]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					ans[nei] = ans[val] + 1
					q.append(nei)
		return ' '.join(map(str, ans[1:]))


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = defaultdict(int)
		graph = defaultdict(list)
		q = deque()
		ans = [1] * n
		for i in range(len(edges)):
			graph[edges[i][0]].append(edges[i][1])
		for i in graph.keys():
			indegree[i] += 0
			for j in graph[i]:
				indegree[j] += 1
		for i in indegree.keys():
			if indegree[i] == 0:
				q.append(i)
		while q:
			x = q.popleft()
			for i in graph[x]:
				indegree[i] -= 1
				if indegree[i] <= 0:
					ans[i - 1] = 1 + ans[x - 1]
					q.append(i)
		return ' '.join(map(str, ans))


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		(times, in_deg_arr, q) = ([0 for i in range(n)], [0 for i in range(n)], deque())
		adj_lst = [[] for i in range(n)]
		for (start, end) in edges:
			start -= 1
			end -= 1
			adj_lst[start].append(end)
			in_deg_arr[end] += 1
		for i in range(n):
			if in_deg_arr[i] == 0:
				q.append(i)
		time = 0
		while q:
			time += 1
			curr_sz = len(q)
			for i in range(curr_sz):
				curr_vert = q.popleft()
				times[curr_vert] = str(time)
				for next_vert in adj_lst[curr_vert]:
					in_deg_arr[next_vert] -= 1
					if in_deg_arr[next_vert] == 0:
						q.append(next_vert)
		return ' '.join(times)


from typing import List
from collections import deque
from collections import defaultdict
from typing import List
import heapq

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		indgree = {i: 0 for i in range(n)}
		distance = [float('inf') for i in range(n)]
		for (i, j) in edges:
			graph[i].append(j)
			indgree[j - 1] += 1
		q = []
		for i in range(len(indgree)):
			if indgree[i] == 0:
				q.append(i + 1)
				distance[i] = 1
		while q:
			cur = q.pop(0)
			for nbr in graph[cur]:
				indgree[nbr - 1] -= 1
				if indgree[nbr - 1] == 0:
					q.append(nbr)
					distance[nbr - 1] = 1 + distance[cur - 1]
		arr = [str(i) for i in distance]
		return ' '.join(arr)


from typing import List
import queue

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		g = [[] for i in range(n + 1)]
		indegree = [0 for i in range(n + 1)]
		for i in range(m):
			(x, y) = edges[i]
			g[x].append(y)
			indegree[y] += 1
		ans = [0 for i in range(n + 1)]
		q = queue.Queue()
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.put(i)
				ans[i] = 1
		while not q.qsize() == 0:
			ele = q.get()
			for p in g[ele]:
				indegree[p] -= 1
				if indegree[p] == 0:
					ans[p] = ans[ele] + 1
					q.put(p)
		s = ''
		for i in range(1, n + 1):
			s = s + ' ' + str(ans[i])
		return ' '.join(s.split())


from typing import List
from queue import Queue
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n)]
		indeg = [0 for i in range(n)]
		for edge in edges:
			(i, j) = edge
			adj[i - 1].append(j - 1)
			indeg[j - 1] += 1
		q = Queue()
		for i in range(n):
			deg = indeg[i]
			if deg == 0:
				q.put(i)
		time = 0
		ans = [0 for i in range(n)]
		while not q.empty():
			s = q.qsize()
			time += 1
			for i in range(s):
				temp = q.get()
				ans[temp] = time
				for nbr in adj[temp]:
					indeg[nbr] -= 1
					if indeg[nbr] == 0:
						q.put(nbr)
		return ' '.join((str(a) for a in ans))


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indeg = [0 for _ in range(n)]
		adj = dict()
		for i in range(n):
			adj[i] = []
		for (x, y) in edges:
			x -= 1
			y -= 1
			adj[x].append(y)
		for (x, y) in edges:
			x -= 1
			y -= 1
			indeg[y] += 1
		start = []
		for (idx, x) in enumerate(indeg):
			if x == 0:
				start.append(idx)
		time = [-1 for _ in range(n)]
		t = 0
		start1 = [x for x in start]
		while len(start1) > 0:
			t += 1
			for x in start1:
				time[x] = t
			start = [x for x in start1]
			start1 = []
			while len(start) > 0:
				node = start[0]
				start.pop(0)
				for child in adj[node]:
					indeg[child] -= 1
					if indeg[child] == 0:
						start1.append(child)
		time = [str(x) for x in time]
		return ' '.join(time)


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		oblig = [0 for i in range(n + 1)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			oblig[edge[1]] += 1
		q = []
		for i in range(1, n + 1):
			if oblig[i] == 0:
				q.append(i)
		times = [1 for i in range(n + 1)]
		while q:
			parent = q.pop(0)
			time = times[parent]
			for child in adj[parent]:
				oblig[child] -= 1
				if oblig[child] == 0:
					times[child] = time + 1
					q.append(child)
		times = times[1:]
		return ' '.join(map(str, times))


from typing import List
from typing import List

class Solution:

	def create(self, edges, m, n):
		graph = [[] for i in range(n + 1)]
		for i in range(m):
			graph[edges[i][0]].append(edges[i][1])
		return graph

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = self.create(edges, m, n)
		n += 1
		indegree = [0] * n
		for i in range(n):
			for j in graph[i]:
				indegree[j] += 1
		queue = []
		ans = [0] * n
		for i in range(1, len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
				ans[i] = 1
		while queue:
			n = queue.pop(0)
			for j in graph[n]:
				indegree[j] -= 1
				if indegree[j] == 0:
					ans[j] = ans[n] + 1
					queue.append(j)
		ans = ans[1:]
		st = ''
		for i in ans:
			st += str(i) + ' '
		return st


from typing import List
from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		h = deque()
		graph = [[] for i in range(n + 1)]
		indegree = [0 for i in range(n + 1)]
		time = [0 for i in range(n)]
		for i in edges:
			graph[i[0]].append(i[1])
			indegree[i[1]] += 1
		for i in range(1, n + 1):
			if not indegree[i]:
				h.append((i, 1))
		while h:
			(node, cost) = h.popleft()
			time[node - 1] = cost
			for i in graph[node]:
				indegree[i] -= 1
				if not indegree[i]:
					h.append((i, cost + 1))
		return ' '.join([str(x) for x in time])

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		edges = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.minimumTime(a[0], a[1], edges)
		print(res)


from typing import List
from typing import List
from collections import defaultdict

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		graph = defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
		indegree = [0] * (n + 1)
		for i in graph:
			for j in graph[i]:
				indegree[j] += 1
		job = [0] * (n + 1)
		q = []
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
				job[i] = 1
		while q:
			cur = q.pop(0)
			for adj in graph[cur]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					job[adj] = 1 + job[cur]
					q.append(adj)
		for i in range(1, n):
			print(job[i], end=' ')
		return job[n]

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		edges = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.minimumTime(a[0], a[1], edges)
		print(res)


from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ind = [0 for _ in range(n + 1)]
		adj = [[] for _ in range(n + 1)] * (n + 1)
		for e in edges:
			adj[e[0]].append(e[1])
		for e in edges:
			ind[e[1]] += 1
		time = [0] * n
		q = []
		for i in range(len(ind)):
			if ind[i] == 0:
				q.append([i, 1])
		while q:
			(i, t) = q.pop(0)
			time[i - 1] = t
			for j in range(len(adj[i])):
				ind[adj[i][j]] -= 1
				if ind[adj[i][j]] == 0:
					q.append([adj[i][j], t + 1])
		ans = ''
		for t in time:
			ans += str(t) + ' '
		return ans

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		edges = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.minimumTime(a[0], a[1], edges)
		print(res)


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		g = [[] for i in range(n + 1)]
		indegree = [0] * (n + 1)
		for (x, y) in edges:
			g[x].append(y)
			indegree[y] += 1
		ans = [0] * (n + 1)
		q = []
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
				ans[i] = 1
		while q:
			val = q.pop(0)
			for nei in g[val]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					ans[nei] = ans[val] + 1
					q.append(nei)
		return ' '.join(map(str, ans[1:]))

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		edges = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.minimumTime(a[0], a[1], edges)
		print(res)


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, V: int, E: int, edges: List[List[int]]) -> int:
		deps = [{} for vertex in range(V + 1)]
		rev_deps = [[] for vertex in range(V + 1)]
		end_time = [-1] * (V + 1)
		for (start, end) in edges:
			deps[end][start] = True
			rev_deps[start].append(end)
		completed = deque()
		for (index, dic) in enumerate(deps):
			if index and (not dic):
				completed.append(index)
				end_time[index] = 1
		while completed:
			current = completed.popleft()
			for task in rev_deps[current]:
				end_time[task] = max(end_time[task], end_time[current] + 1)
				del deps[task][current]
				if not deps[task]:
					completed.append(task)
		return ' '.join([str(i) for i in end_time[1:]])


from typing import List
from queue import Queue
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		q = Queue()
		adj = [[] for i in range(n + 1)]
		indeg = [0 for i in range(n + 1)]
		for edge in edges:
			(u, v) = edge
			indeg[v] += 1
			adj[u].append(v)
		for i in range(1, n + 1):
			if indeg[i] == 0:
				q.put(i)
		count = 0
		ans = [0 for i in range(n)]
		while not q.empty():
			s = q.qsize()
			count += 1
			for i in range(s):
				temp = q.get()
				ans[temp - 1] = count
				for nbr in adj[temp]:
					indeg[nbr] -= 1
					if indeg[nbr] == 0:
						q.put(nbr)
		return ' '.join(map(str, ans))


from typing import List
from typing import List

class Solution:

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

	def add(self, u, v):
		self.d[u].append(v)

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		ind = [0] * (n + 1)
		ind[0] = float('inf')
		for i in edges:
			x = i[0]
			y = i[1]
			ind[y] += 1
		for i in range(n + 1):
			self.d.append([])
		for i in edges:
			self.add(i[0], i[1])
		res = {}
		queue = []
		vis = [False] * (n + 1)
		for i in range(n + 1):
			if ind[i] == 0:
				queue.append((i, 1))
		c = 0
		while c != n + 1 and queue:
			x = queue.pop(0)
			m = x[0]
			ns = x[1]
			if vis[m] == False:
				res[m] = ns
				c += 1
				vis[m] = True
			else:
				continue
			for i in self.d[m]:
				ind[i] -= 1
			for j in range(n + 1):
				if ind[j] == 0 and vis[j] == False:
					queue.append((j, ns + 1))
		r = ''
		for i in res.keys():
			r += str(res[i]) + ' '
		return r


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = [0] * (n + 1)
		jobs = [0] * (n + 1)
		q = deque()
		adj = [[] for i in range(n + 1)]
		for (i, j) in edges:
			adj[i].append(j)
		for i in range(1, n + 1):
			for j in adj[i]:
				indegree[j] = indegree[j] + 1
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
				jobs[i] = 1
		while q:
			node = q.popleft()
			for i in adj[node]:
				indegree[i] = indegree[i] - 1
				if indegree[i] == 0:
					q.append(i)
					jobs[i] = 1 + jobs[node]
		k = jobs[1:]
		return ' '.join((str(i) for i in k))


from typing import List
from collections import defaultdict, deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		degree = defaultdict(int)
		graph = defaultdict(list)
		for (s, e) in edges:
			graph[s].append(e)
			degree[e] += 1
		queue = deque()
		ans = [-1] * n
		for i in range(1, n + 1):
			if degree[i] == 0:
				queue.append(i)
				ans[i - 1] = 1
		while queue:
			node = queue.popleft()
			for adj in graph[node]:
				degree[adj] -= 1
				if degree[adj] == 0:
					queue.append(adj)
					ans[adj - 1] = ans[node - 1] + 1
		return ' '.join((str(i) for i in ans))


from typing import List
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

	def minimumTime(self, V: int, E: int, edges: List[List[int]]) -> int:
		indegree = [0] * (V + 1)
		graph = defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
		for i in graph:
			for j in graph[i]:
				indegree[j] += 1
		job = [0] * (V + 1)
		q = deque([])
		for i in range(1, V + 1):
			if indegree[i] == 0:
				q.append(i)
				job[i] = 1
		while q:
			cur = q.popleft()
			for adj in graph[cur]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					job[adj] = 1 + job[cur]
					q.append(adj)
		for i in range(1, V + 1):
			print(job[i], end=' ')
		return ''


from typing import List

class Solution:

	def __init__(self):
		self.graph = []
		self.res = []

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		incoming = [0 for i in range(n + 1)]
		graph = {i: [] for i in range(1, n + 1)}
		res = [-1 for i in range(n + 1)]
		for i in edges:
			graph[i[0]].append(i[1])
			incoming[i[1]] += 1
		queue = [i for i in range(1, n + 1) if incoming[i] == 0]
		for i in queue:
			res[i] = 1
		while len(queue) > 0:
			node = queue.pop(0)
			for i in graph[node]:
				incoming[i] -= 1
				if incoming[i] == 0:
					queue.append(i)
					res[i] = res[node] + 1
		res = [str(i) for i in res]
		return ' '.join(res[1:])

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		edges = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.minimumTime(a[0], a[1], edges)
		print(res)


from typing import List

class Solution:

	def __init__(self):
		self.graph = []
		self.res = []

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		incoming = [0 for i in range(n + 1)]
		graph = {i: [] for i in range(1, n + 1)}
		res = [-1 for i in range(n + 1)]
		for i in edges:
			graph[i[0]].append(i[1])
			incoming[i[1]] += 1
		queue = [i for i in range(1, n + 1) if incoming[i] == 0]
		for i in queue:
			res[i] = 1
		while len(queue) > 0:
			node = queue.pop(0)
			for i in graph[node]:
				incoming[i] -= 1
				if incoming[i] == 0:
					queue.append(i)
					res[i] = res[node] + 1
		res = [str(i) for i in res]
		return ' '.join(res[1:])


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		time = [0 for _ in range(n)]
		count = 0
		indegree = [0 for _ in range(n + 1)]
		adj = [[] for _ in range(n + 1)]
		for (u, v) in edges:
			indegree[v] += 1
			adj[u].append(v)
		import queue
		q = queue.Queue()
		for i in range(len(indegree)):
			if indegree[i] == 0:
				q.put(i)
		while not q.empty():
			count += 1
			k = q.qsize()
			while k > 0:
				n = q.get()
				time[n - 1] = count
				for neigh in adj[n]:
					indegree[neigh] -= 1
					if indegree[neigh] == 0:
						q.put(neigh)
				k -= 1
		return ' '.join([str(t) for t in time])


from typing import List
from collections import deque

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		adj = [[] for i in range(n + 1)]
		indig = [0 for i in range(n + 1)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
			indig[edge[1]] += 1
		res = [0 for i in range(n + 1)]
		cnt = 1
		q = deque()

		def fill(q, indig):
			for i in range(1, len(indig)):
				if indig[i] == 0:
					q.append(i)
		fill(q, indig)
		tot = 0
		while tot != n:
			val = q.popleft()
			indig[val] = -1
			res[val] = cnt
			tot += 1
			for ver in adj[val]:
				indig[ver] -= 1
			if len(q) == 0:
				cnt += 1
				fill(q, indig)
		ans = ''
		for i in range(1, len(res)):
			ans += str(res[i])
			ans += ' '
		return ans[:-1]


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		from collections import deque
		q = deque()
		G = {}
		incoming = [0 for i in range(n)]
		for i in range(n):
			G[i] = set()
		for (x, y) in edges:
			G[x - 1].add(y - 1)
			incoming[y - 1] += 1
		for i in range(n):
			if incoming[i] == 0:
				q.append((i, 1))
		ans = [0 for i in range(n)]
		while q:
			(i, time) = q.popleft()
			ans[i] = time
			for x in G[i]:
				incoming[x] -= 1
				if incoming[x] == 0:
					q.append((x, time + 1))
		return ' '.join([str(x) for x in ans])


from typing import List
from typing import List
from collections import defaultdict, deque

class Graph:

	def __init__(self, vertices, edges):
		self.graph = defaultdict(list)
		self.n = vertices
		self.m = edges

	def addEdge(self, u, v):
		self.graph[u].append(v)

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		g = Graph(n, m)
		for edge in edges:
			g.addEdge(edge[0], edge[1])
		inDegree = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in g.graph[i]:
				inDegree[j] += 1
		job = [0 for _ in range(n + 1)]
		q = deque()
		for i in range(1, n + 1):
			if inDegree[i] == 0:
				q.append(i)
				job[i] = 1
		while q:
			curr = q.popleft()
			for adj in g.graph[curr]:
				inDegree[adj] -= 1
				if inDegree[adj] == 0:
					q.append(adj)
					job[adj] = job[curr] + 1
		for ele in job[1:]:
			print(ele, end=' ')
		return ''


from typing import List
from typing import List

class Solution:

	def minimumTime(self, n: int, m: int, edges: List[List[int]]) -> int:
		indegree = [0 for i in range(n + 1)]
		adj = [[] for i in range(n + 1)]
		for i in edges:
			indegree[i[1]] += 1
			adj[i[0]].append(i[1])
		q = []
		for i in range(1, n + 1):
			if indegree[i] == 0:
				q.append(i)
		res = [0 for i in range(n + 1)]
		dist = 1
		tempq = []
		while q:
			v = q.pop(0)
			res[v] = dist
			for i in adj[v]:
				indegree[i] -= 1
				if indegree[i] == 0:
					tempq.append(i)
			if len(q) == 0:
				q = tempq
				dist += 1
				tempq = []
		res = res[1:]
		res1 = ''
		for i in res:
			res1 += str(i)
			res1 += ' '
		return res1[:-1]