The minions are very elitist in nature. If minion x admires minion y, then y thinks too highly of himself and does not admire x back. Also, if x admires y, x also admires everyone that y admires.
All the minions are going to be present at the Villain Con. They want to make sure that they do not dress in the same color as someone who admires them. 
There are N minions and M relations between them. The relations are given in a 2D array mat. Each relation is given in x_{i} , y_{i} format where y_{i} admires x_{i. }Find the minimum number of different colours that the minions will be dressing in. 
 
Example 1:
Input: 
N = 5, M = 6
mat = {{1, 3}, 
       {2, 3}, 
       {3, 4}, 
       {1, 4}, 
       {2, 5}, 
       {3, 5}}
Output: 3
Explaination:
If we assign red colour to 1 and 2,
green colour to 3, and blue colour to 4 and 5, then
every minion will have different coloured dresses
from the one who admires them.
Example 2:
Input:
N = 3, M = 2
mat = {{1,3},{2,3}}
Output:
2
Explanation:
If we assign red colour to 1 and 2, and green colour to 3, then the condition is satisfied.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minColour() which takes N, M and mat[][] as input parameters and returns the minimum number of colours required.
 
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ M ≤ 2*10^{5}  
1 ≤ x_{i} , y_{i} ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def minColour(self, N, M, mat):

        # code here

Solutions:
from collections import deque

class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for _ in range(N)]
		degree = [0] * N
		dist = [0] * N
		for m in mat:
			degree[m[0] - 1] += 1
			adj[m[1] - 1].append(m[0] - 1)
		q = deque()
		for i in range(N):
			if degree[i] == 0:
				q.append(i)
		while len(q) > 0:
			v = q.popleft()
			for w in adj[v]:
				degree[w] -= 1
				dist[w] = max(dist[w], dist[v] + 1)
				if degree[w] == 0:
					q.append(w)
		return max(dist) + 1


from collections import deque

class Solution:

	def minColour(self, N, M, mat):
		indegree = [0] * (N + 1)
		adj = [[] for i in range(N + 1)]
		for i in mat:
			adj[i[1]].append(i[0])
			indegree[i[0]] += 1
		que = deque()
		for i in range(1, N + 1):
			if indegree[i] == 0:
				que.append(i)
		lev = 0
		while que:
			lev += 1
			for i in range(len(que)):
				x = que.popleft()
				for i in adj[x]:
					indegree[i] -= 1
					if indegree[i] == 0:
						que.append(i)
		return lev


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for _ in range(N)]
		indeg = [0] * N
		for (u, v) in mat:
			adj[u - 1].append(v - 1)
			indeg[v - 1] += 1
		visited = [False] * (N + 1)
		res = float('-inf')
		q = []
		for s in range(N):
			if indeg[s] == 0:
				q.append(s)
				visited[s] = True
		res = self.bfs(q, adj, visited, indeg)
		return res

	def bfs(self, q, adj, visited, indeg):
		level = 0
		while q:
			levelLen = len(q)
			for _ in range(levelLen):
				curr = q.pop(0)
				for ngbr in adj[curr]:
					indeg[ngbr] -= 1
					if not visited[ngbr] and indeg[ngbr] == 0:
						visited[ngbr] = True
						q.append(ngbr)
			level += 1
		return level


class Solution:

	def minColour(self, N, M, mat):
		startbyDestArr = [[] for i in range(N)]
		startArr = [0] * N
		q = []
		for (start, dest) in mat:
			startbyDestArr[dest - 1].append(start - 1)
			startArr[start - 1] += 1
		for i in range(N):
			if startArr[i] == 0:
				q.append(i)
		for color in range(N):
			if len(q) == 0:
				return color
			for i in range(len(q)):
				for start in startbyDestArr[q.pop(0)]:
					startArr[start] -= 1
					if startArr[start] == 0:
						q.append(start)


class Solution:

	def minColour(self, N, M, mat):
		visited = [False for i in range(N + 1)]
		length_chain = [0 for i in range(N + 1)]
		grid = {}
		for i in mat:
			(s, d) = (i[0], i[1])
			if s not in grid:
				grid[s] = [d]
			else:
				grid[s].append(d)
			if d not in grid:
				grid[d] = []

		def solver(v, grid):
			visited[v] = True
			if length_chain[v] != 0:
				return length[v]
			output = 0
			for k in grid[v]:
				if visited[k] == False:
					output = max(output, solver(k, grid))
				elif length_chain[k] != 0:
					output = max(output, length_chain[k])
			length_chain[v] = output + 1
			return output + 1
		for i in grid:
			if visited[i] == False:
				solver(i, grid)
		return max(length_chain)


import sys
sys.setrecursionlimit(100000)

def recur(u, adj, L):
	sub = 0
	for v in adj[u]:
		if L[v] == -1:
			recur(v, adj, L)
		sub = max(sub, L[v])
	L[u] = sub + 1

class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for _ in range(N)]
		for (d, s) in mat:
			d -= 1
			s -= 1
			adj[s].append(d)
		L = [-1] * N
		for i in range(N):
			if L[i] != -1:
				continue
			L[i] = 0
			recur(i, adj, L)
		return max(L)


class Solution:

	def minColour(self, N, M, mat):
		adj = {}
		distance = [-1 for _ in range(N + 1)]
		for i in range(M):
			if mat[i][0] not in adj:
				adj[mat[i][0]] = [mat[i][1]]
			else:
				adj[mat[i][0]].append(mat[i][1])
		dist = 0
		res = 0
		for i in range(N + 1):
			dist = self.DFS(distance, adj, i)
			res = max(res, dist)
		return res

	def DFS(self, distance, adj, node):
		if distance[node] != -1:
			return distance[node]
		if node in adj and len(adj[node]) == 0:
			distance[node] = 1
			return distance[node]
		dist = 0
		if node in adj:
			for x in adj[node]:
				dist = max(dist, self.DFS(distance, adj, x))
		distance[node] = dist + 1
		return dist + 1


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for i in range(N + 1)]
		lenn = [0 for i in range(N + 1)]
		maxVal = -1
		for i in mat:
			adj[i[0]].append(i[1])
		for i in range(1, N + 1):
			maxVal = max(maxVal, self.rec(i, adj, lenn))
		return maxVal

	def rec(self, n, adj, lenn):
		if lenn[n]:
			return lenn[n]
		lenn[n] = 0
		for u in adj[n]:
			lenn[n] = max(lenn[n], self.rec(u, adj, lenn))
		lenn[n] = lenn[n] + 1
		return lenn[n]


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for _ in range(N + 1)]
		visit = [False] * (N + 1)
		dist = [0] * (N + 1)
		for (u, v) in mat:
			adj[u].append(v)
		for i in range(1, N + 1):
			if not visit[i]:
				self.dfs(i, adj, visit, dist)
		return max(dist)

	def dfs(self, x, adj, visit, dist):
		visit[x] = True
		chain_len = 0
		for v in adj[x]:
			if not visit[v]:
				self.dfs(v, adj, visit, dist)
			chain_len = max(chain_len, dist[v])
		dist[x] = chain_len + 1


class Solution:

	def minColour(self, n, m, e, printDists=False):
		vertices = set()
		parents = {}
		children = {}
		for ed in e:
			if ed[0] in children:
				children[ed[0]].add(ed[1])
			else:
				children[ed[0]] = set([ed[1]])
			if ed[1] in parents:
				parents[ed[1]].add(ed[0])
			else:
				parents[ed[1]] = set([ed[0]])
			vertices.add(ed[0])
			vertices.add(ed[1])
		s = set()
		for v in vertices:
			if not v in parents:
				s.add(v)
				parents[v] = set()
			if not v in children:
				children[v] = set()
		ts = []
		tempChildren = {}
		tempParents = {}
		for x in children:
			tempChildren[x] = set(children[x])
		for x in parents:
			tempParents[x] = set(parents[x])
		while len(s) > 0:
			u = s.pop()
			ts.append(u)
			c = list(tempChildren[u])
			for v in c:
				tempChildren[u].pop()
				tempParents[v].pop()
				if len(tempParents[v]) == 0:
					s.add(v)
		dists = {}
		for v in ts:
			if len(parents[v]) == 0:
				dists[v] = 0
			else:
				dists[v] = 1 + max([dists[x] for x in parents[v]])
		if printDists:
			print('Distances = %r' % dists)
		return 1 + max([dists[x] for x in ts])


from collections import defaultdict

class Solution:

	def dfs(self, node, dist, grph):
		dist[node] = 0
		chain = 0
		for n in grph[node]:
			if dist[n] == -1:
				self.dfs(n, dist, grph)
			chain = max(chain, dist[n])
		dist[node] = chain + 1

	def minColour(self, N, M, mat):
		graph = defaultdict(list)
		dist = [-1] * (N + 1)
		for (u, v) in mat:
			graph[u].append(v)
		for node in range(1, N + 1):
			self.dfs(node, dist, graph)
		return max(dist)


class Solution:

	def minColour(self, N, M, mat):
		in_degrees = [0] * (N + 1)
		for admire in mat:
			in_degrees[admire[0]] += 1
		from collections import deque
		minions = deque()
		for i in range(1, N + 1):
			if in_degrees[i] == 0:
				minions.append(i)
		from collections import defaultdict
		adj_mat = defaultdict(list)
		for admire in mat:
			adj_mat[admire[1]].append(admire[0])
		ans = 0
		while len(minions) != 0:
			k = len(minions)
			for i in range(k):
				node = minions.popleft()
				for admiree in adj_mat[node]:
					if in_degrees[admiree] >= 1:
						in_degrees[admiree] -= 1
						if in_degrees[admiree] == 0:
							minions.append(admiree)
			ans += 1
		return ans


from collections import defaultdict

class Solution:

	def minColour(self, N, M, mat):
		adjMat = defaultdict(list)
		indegree = [0 for _ in range(N)]
		q = []
		for i in mat:
			adjMat[i[1] - 1].append(i[0] - 1)
			indegree[i[0] - 1] += 1
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		for color in range(N):
			if len(q) == 0:
				return color
			for i in range(len(q)):
				for start in adjMat[q.pop(0)]:
					indegree[start] -= 1
					if indegree[start] == 0:
						q.append(start)


from collections import defaultdict

class Solution:

	def minColour(self, N, M, mat):
		ind = [0 for i in range(N + 1)]
		g = defaultdict(list)
		for (x, y) in mat:
			g[x].append(y)
			ind[y] += 1
		q = []
		for i in range(1, N + 1):
			if ind[i] == 0:
				q.append(i)
		l = 0
		while q:
			l += 1
			for i in range(len(q)):
				x = q.pop(0)
				for j in g[x]:
					ind[j] -= 1
					if ind[j] == 0:
						q.append(j)
		return l


class Solution:

	def minColour(self, N, M, mat):

		def dfs(node):
			vis[node] = True
			distt = 0
			for x in adj[node]:
				if vis[x] == False:
					dfs(x)
				distt = max(distt, dis[x])
			dis[node] = distt + 1
		adj = [[] for _ in range(N + 1)]
		vis = [False] * (N + 1)
		dis = [0] * (N + 1)
		for (x, y) in mat:
			adj[x].append(y)
		for i in range(N + 1):
			if vis[i] == False:
				dfs(i)
		return max(dis)


class Solution:

	def rec(self, n, adj, lenn):
		if lenn[n]:
			return lenn[n]
		lenn[n] = 0
		for neight in adj[n]:
			lenn[n] = max(lenn[n], self.rec(neight, adj, lenn))
		lenn[n] += 1
		return lenn[n]

	def minColour(self, N, M, mat):
		adj = [[] for i in range(N + 1)]
		lenn = [0 for i in range(N + 1)]
		for i in mat:
			adj[i[0]].append(i[1])
		maxcl = -1
		for i in range(1, N + 1):
			maxcl = max(maxcl, self.rec(i, adj, lenn))
		return maxcl


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def recur(self, v, adj, dp):
		if dp[v] != 0:
			return dp[v]
		res = 1
		for u in adj[v]:
			res = max(res, self.recur(u, adj, dp) + 1)
		dp[v] = res
		return dp[v]

	def minColour(self, N, M, mat):
		adj = defaultdict(list)
		dp = [0 for i in range(N + 1)]
		for i in range(M):
			adj[mat[i][1]].append(mat[i][0])
		ans = 0
		for i in range(1, N + 1):
			ans = max(ans, self.recur(i, adj, dp))
		return ans


from collections import *
from heapq import *

class Solution:

	def minColour(self, n, m, a):
		inf = 10000000000
		d = defaultdict(list)
		val = [0] * n
		for (x, y) in a:
			x -= 1
			y -= 1
			d[y].append(x)
			val[x] += 1
		q = []
		for i in range(n):
			if val[i] == 0:
				heappush(q, [0, i])
		ans = [0] * n
		while q:
			(v, s) = heappop(q)
			for node in d[s]:
				val[node] -= 1
				if val[node] == 0:
					ans[node] = v + 1
					heappush(q, [v + 1, node])
		return max(ans) + 1


from collections import defaultdict as dc

class Solution:

	def minColour(self, N, M, mat):
		adj = dc(list)
		p = dc(int)
		for i in range(M):
			adj[mat[i][1]].append(mat[i][0])
		vis = dc(int)

		def dfs(i, N, adj, d):
			vis[i] = 1
			p[i] = 0
			for x in adj[i]:
				if vis[x] == 0:
					dfs(x, N, adj, d + 1)
				p[i] = max(p[i], p[x])
			p[i] += 1
		for i in range(1, N + 1):
			if vis[i] == 0:
				dfs(i, N, adj, 1)
		return max(p.values())


from collections import defaultdict

class Solution:

	def minColour(self, N, M, mat):
		edges = defaultdict(list)
		degree = [0 for i in range(N + 1)]
		for i in mat:
			edges[i[0]].append(i[1])
			degree[i[1]] += 1
		level = 0
		q = []
		for i in range(1, N + 1):
			if degree[i] == 0:
				q.append(i)
		if len(q) == 0:
			return 0
		while q:
			size = len(q)
			for i in range(size):
				node = q.pop(0)
				for k in edges[node]:
					degree[k] -= 1
					if degree[k] == 0:
						q.append(k)
				degree[node] -= 1
			level += 1
		return level


from collections import defaultdict, Counter

class Solution:

	def minColour(self, N, M, mat):
		adj = defaultdict(list)
		indeg = Counter()
		for i in range(M):
			adj[mat[i][0]] += [mat[i][1]]
			indeg[mat[i][1]] += 1
		q = []
		for i in range(1, N + 1):
			if indeg[i] == 0:
				q.append(i)
		q.append(-1)
		cnt = 0
		while q:
			x = q.pop(0)
			if x == -1:
				cnt += 1
				if len(q) == 0:
					break
				x = q.pop(0)
				q.append(-1)
			for i in adj[x]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		return cnt


class Solution:

	def minColour(self, N, M, mat):
		graph = {i: [] for i in range(1, N + 1)}
		for (i, j) in mat:
			graph[i].append(j)
		indegs = [0] * (N + 1)
		for (i, j) in mat:
			indegs[j] += 1
		q = [i for i in range(1, N + 1) if not indegs[i]]
		res = 0
		while q:
			res += 1
			sz = len(q)
			while sz:
				ele = q.pop(0)
				for i in graph[ele]:
					indegs[i] -= 1
					if not indegs[i]:
						q.append(i)
				sz -= 1
		return res


class Solution:

	def minColour(self, numNodes, numEdges, edges):
		graph = [[] for _ in range(numNodes + 1)]
		for edge in edges:
			graph[edge[0]].append(edge[1])
		self.dp = [0 for n in range(numNodes + 1)]
		self.graph = graph
		for n in range(1, numNodes + 1):
			self.dfs(n)
		return max(self.dp)

	def dfs(self, node):
		if self.dp[node]:
			return self.dp[node]
		res = 0
		for adj in self.graph[node]:
			res = max(self.dfs(adj), res)
		self.dp[node] = res + 1
		return self.dp[node]


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for _ in range(N + 1)]
		vis = [False] * (N + 1)
		dis = [0] * (N + 1)
		for (u, v) in mat:
			adj[u].append(v)
		for i in range(1, N + 1):
			if not vis[i]:
				self.dfs(i, adj, vis, dis)
		return max(dis)

	def dfs(self, x, adj, vis, dis):
		vis[x] = True
		chainlen = 0
		for v in adj[x]:
			if not vis[v]:
				self.dfs(v, adj, vis, dis)
			chainlen = max(chainlen, dis[v])
		dis[x] = chainlen + 1


from collections import defaultdict

class Solution:

	def minColour(self, n, m, l):

		def f():
			return []
		g = defaultdict(f)
		ans = [0]
		for i in l:
			g[i[1]].append(i[0])
		dp = [0 for i in range(n + 1)]

		def fun(ans, dp, i):
			if dp[i] != 0:
				return dp[i]
			dp[i] = 1
			for j in g[i]:
				dp[i] = max(dp[i], 1 + fun(ans, dp, j))
			ans[0] = max(ans[0], dp[i])
			return dp[i]
		for i in range(1, n + 1):
			if dp[i] == 0:
				ans[0] = max(ans[0], fun(ans, dp, i))
		return ans[0]


from collections import defaultdict, deque

class Solution:

	def minColour(self, n, m, mat):
		adj = defaultdict(list)
		indeg = [0] * (n + 1)
		for (x, y) in mat:
			adj[x].append(y)
			indeg[y] += 1
		queue = deque()
		color = 0
		for i in range(1, n + 1):
			if indeg[i] == 0:
				queue.append(i)
		if not queue:
			return 0
		while queue:
			size = len(queue)
			for _ in range(size):
				node = queue.popleft()
				for nbr in adj[node]:
					indeg[nbr] -= 1
					if indeg[nbr] == 0:
						queue.append(nbr)
			color += 1
		return color


class Solution:

	def minColour(self, N, M, mat):
		adj = {}
		indegree = {}
		for edge in mat:
			if edge[0] not in adj:
				adj[edge[0]] = set()
			adj[edge[0]].add(edge[1])
			if edge[1] not in indegree:
				indegree[edge[1]] = 0
			indegree[edge[1]] += 1
		q = []
		for i in range(1, N + 1):
			if i not in indegree:
				q.append(i)
			if i not in adj:
				adj[i] = set()
		ans = 0
		while q:
			n = len(q)
			for i in range(n):
				r = q.pop(0)
				for nb in adj[r]:
					indegree[nb] -= 1
					if indegree[nb] == 0:
						q.append(nb)
			ans += 1
		return ans


from queue import Queue
from collections import defaultdict

class Solution:

	def minColour(self, N, M, mat):
		vertices = defaultdict(int)
		depth = defaultdict(int)
		for v in range(1, N + 1):
			vertices[v] = 0
			depth[v] = 0
		adj = defaultdict(list)
		for edge in mat:
			vertices[edge[0]] += 1
			adj[edge[1]].append(edge[0])
		queue = [k for (k, v) in vertices.items() if v == 0]
		count = 0
		top_order = []
		colors = {v: 0 for v in queue}
		while queue:
			u = queue.pop(0)
			top_order.append(u)
			for a in adj[u]:
				colors[a] = colors.get(u, -1) + 1
				depth[a] += 1
				vertices[a] -= 1
				if vertices[a] == 0:
					queue.append(a)
			count += 1
		if count != N:
			return -1
		else:
			return len(set(colors.values()))


from collections import deque

class Solution:

	def minColour(self, N, M, mat):
		adj_list = [[] for _ in range(N)]
		inn = [0] * N
		dep = [-1] * N
		ans = 1
		for i in range(M):
			adj_list[mat[i][0] - 1].append(mat[i][1] - 1)
			inn[mat[i][1] - 1] += 1
		que = deque()
		for i in range(N):
			if inn[i] == 0:
				que.append(i)
				dep[i] = 1
		while que:
			u = que.popleft()
			for v in adj_list[u]:
				inn[v] -= 1
				dep[v] = max(dep[v], 1 + dep[u])
				if inn[v] == 0:
					que.append(v)
		return max(dep)


from collections import *

class Solution:

	def __init__(self):
		self.ans = 0

	def minColour(self, n, m, matrix):

		def dfs(i, s):
			vis[i] = 1
			for j in d[i]:
				if vis[j] == 0:
					dis[i] = dfs(j, s + 1)
				else:
					dis[i] = max(dis[j] + 1, dis[i])
			return dis[i] + 1
		d = defaultdict(list)
		for i in matrix:
			d[i[1]].append(i[0])
		ans = 0
		dis = [0 for i in range(n + 1)]
		vis = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if vis[i] == 0:
				dfs(i, 0)
		return max(dis) + 1


from collections import deque

class Solution:

	def minColour(self, N, M, mat):
		from collections import defaultdict
		edges = defaultdict(list)
		indgree = [0] * (N + 1)
		for (u, v) in mat:
			edges[u].append(v)
			indgree[v] += 1
		visited = [False] * (N + 1)
		level = 0
		queue = deque()
		for i in range(1, N + 1):
			if indgree[i] == 0:
				queue.append(i)
		if len(queue) == 0:
			return 0
		while queue:
			for i in range(len(queue)):
				node = queue.popleft()
				for nei in edges[node]:
					indgree[nei] -= 1
					if indgree[nei] == 0:
						queue.append(nei)
			level += 1
		return level


from collections import deque

class Solution:

	def minColour(self, N, M, mat):
		g = [[] for _ in range(N)]
		for i in mat:
			g[i[1] - 1].append(i[0] - 1)
		h = [-1] * N

		def dfs(x):
			if h[x] != -1:
				return h[x]
			c = 0
			for y in g[x]:
				c = max(c, dfs(y))
			h[x] = c + 1
			return h[x]
		for i in range(N):
			dfs(i)
		return max(h)


from collections import defaultdict

class Solution:

	def minColour(self, N, M, mat):
		adj = defaultdict(list)
		for (i, j) in mat:
			adj[j].append(i)
		visited = [False] * (N + 1)
		topo = []

		def dfs(src):
			visited[src] = True
			for child in adj[src]:
				if visited[child] == False:
					dfs(child)
			topo.append(src)
		for i in range(1, N + 1):
			dfs(i)
		dist = [1] * (N + 1)
		while topo:
			u = topo.pop()
			for v in adj[u]:
				if dist[v] < dist[u] + 1:
					dist[v] = dist[u] + 1
		return max(dist)


class Solution:
	ans = 0

	def minColour(self, N, M, mat):
		graph = [[] for _ in range(N + 1)]
		indeg = [0] * (N + 1)
		for (v, u) in mat:
			graph[u].append(v)
			indeg[v] += 1
		q = []
		for i in range(1, N + 1):
			if indeg[i] == 0:
				q.append(i)
		ans = 0
		while q:
			next_level = []
			ans += 1
			for cur in q:
				for neighbor in graph[cur]:
					indeg[neighbor] -= 1
					if indeg[neighbor] == 0:
						next_level.append(neighbor)
			q = next_level
		return ans


class Solution:

	def minColour(self, N, M, mat):
		(graph, top) = self.buildFollowerGraph(N, mat)
		checked = set()
		followers = [0] * (N + 1)
		for i in top:
			self.countFollowers(i, graph, checked, followers)
		return max(followers)

	def buildFollowerGraph(self, N, mat):
		graph = [[] for _ in range(N + 1)]
		top = set()
		for i in range(1, N + 1):
			top.add(i)
		for (x, y) in mat:
			graph[y].append(x)
			if x in top:
				top.remove(x)
		return (graph, top)

	def countFollowers(self, i, graph, checked, followers):
		if i in checked:
			return followers[i]
		for child in graph[i]:
			followers[i] = max(followers[i], self.countFollowers(child, graph, checked, followers))
		followers[i] += 1
		checked.add(i)
		return followers[i]


class Solution:

	def minColour(self, N, M, mat):
		indeg = [0] * N
		color = [1] * N
		adj = {}
		for u in range(N):
			adj[u] = set()
		for (u, v) in mat:
			adj[u - 1].add(v - 1)
			indeg[v - 1] += 1
		from collections import deque
		q = deque()
		for i in range(N):
			if indeg[i] == 0:
				q.append(i)
		while q:
			u = q.popleft()
			for v in adj[u]:
				indeg[v] -= 1
				if indeg[v] == 0:
					q.append(v)
				if color[v] <= color[u]:
					color[v] = color[u] + 1
		ans = -1
		for i in range(N):
			ans = max(ans, color[i])
		return ans


class Solution:

	def bfs(self, a, m):
		q = []
		l = 0
		indegree = [0 for i in range(len(a))]
		for i in range(len(a)):
			for j in a[i]:
				indegree[j] += 1
		for i in range(1, len(a)):
			if indegree[i] == 0:
				q.append(i)
		while q:
			for i in range(len(q)):
				n = q.pop(0)
				for j in a[n]:
					indegree[j] -= 1
					if indegree[j] == 0:
						q.append(j)
			l += 1
		return l

	def minColour(self, N, M, mat):
		ad = [[] for i in range(N + 1)]
		for i in range(M):
			ad[mat[i][0]].append(mat[i][1])
		r = self.bfs(ad, M)
		return r


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for i in range(N + 1)]
		deg = [0] * (N + 1)
		visited = [False] * (N + 1)
		for i in range(M):
			adj[mat[i][1]].append(mat[i][0])
			deg[mat[i][0]] += 1
		q = []
		for i in range(1, N + 1):
			if deg[i] == 0:
				q.append(i)
		ans = 0
		while q:
			n = len(q)
			for i in range(n):
				x = q.pop(0)
				visited[x] = True
				for ele in adj[x]:
					deg[ele] -= 1
					if deg[ele] == 0:
						q.append(ele)
			ans += 1
		for i in range(1, N + 1):
			ans += visited[i] == False
		return ans


class Solution:

	def minColour(self, N, M, mat):
		in_deg = [0] * (N + 1)
		adj = {}
		for i in range(1, N + 1):
			adj[i] = []
		for i in range(M):
			(x, y) = mat[i]
			adj[y].append(x)
			in_deg[x] += 1
		q = []
		for i in range(1, N + 1):
			if in_deg[i] == 0:
				q.append((i, 1))
		max_cnt = -1
		while len(q):
			cur = q[0]
			q = q[1:]
			(node, cnt) = cur
			max_cnt = max(max_cnt, cnt)
			for j in adj[node]:
				in_deg[j] -= 1
				if in_deg[j] == 0:
					q.append((j, cnt + 1))
		return max_cnt


class Solution:

	def minColour(self, N, M, mat):
		color = [-1] * N
		graph = {i: [] for i in range(1, N + 1)}
		ind = [0] * (N + 1)
		ind[0] = -1
		for (i, j) in mat:
			graph[j].append(i)
			ind[i] += 1
		q = []
		for i in range(1, N + 1):
			if ind[i] == 0:
				q.append(i)
		ans = 0
		while q:
			s = len(q)
			ans += 1
			for i in range(s):
				curr = q.pop(0)
				for j in graph[curr]:
					ind[j] -= 1
					if ind[j] == 0:
						q.append(j)
		return ans


from collections import *
from functools import *

class Solution:

	def minColour(self, n, m, a):
		adj = defaultdict(list)
		indegree = [0] * (n + 1)
		for [x, y] in a:
			adj[y].append(x)
			indegree[x] += 1
		q = deque([])
		for k in range(1, n + 1):
			if indegree[k] == 0:
				q.append(k)
		res = 0
		while q:
			res += 1
			t = len(q)
			while t:
				node = q.popleft()
				for child in adj[node]:
					indegree[child] -= 1
					if indegree[child] == 0:
						q.append(child)
				t -= 1
		return res


class Solution:

	def minColour(self, V, E, mat):
		adj = [[] for _ in range(V)]
		for p in mat:
			adj[p[1] - 1].append(p[0] - 1)
		ans = 0
		cache = {}

		def dfs(u):
			if u in cache:
				return cache[u]
			if not adj[u]:
				cache[u] = 1
				return 1
			ans = 1
			for v in adj[u]:
				ans = max(ans, 1 + dfs(v))
			cache[u] = ans
			return ans
		for v in range(V):
			ans = max(ans, dfs(v))
		return ans


class Node:

	def __init__(self, value):
		self.data = value
		self.admires = []

class Solution:

	def findDepth(self, root, dt):
		if len(root.admires) == 0:
			return 1
		if root.data in dt:
			return dt[root.data]
		mx = 0
		for i in range(len(root.admires)):
			mx = max(mx, self.findDepth(root.admires[i], dt))
		dt[root.data] = mx + 1
		return mx + 1

	def minColour(self, N, M, mat):
		nodes = []
		for i in range(N):
			nodes.append(Node(i + 1))
		for i in range(M):
			nodes[mat[i][1] - 1].admires.append(nodes[mat[i][0] - 1])
		ans = 1
		dt = dict()
		for i in range(N):
			ans = max(ans, self.findDepth(nodes[i], dt))
		return ans


class Solution:

	def dfs(self, node, graph, visited, colors):
		visited[node] = True
		maxColor = 0
		for child in graph[node]:
			if not visited[child]:
				self.dfs(child, graph, visited, colors)
			maxColor = max(maxColor, colors[child])
		colors[node] = maxColor + 1

	def minColour(self, n, m, mat):
		graph = [[] for _ in range(n + 1)]
		visited = [False for _ in range(n + 1)]
		colors = [0 for _ in range(n + 1)]
		for edge in mat:
			u = edge[0]
			v = edge[1]
			graph[v].append(u)
		for i in range(1, n + 1):
			if not visited[i]:
				self.dfs(i, graph, visited, colors)
		return max(colors)


class Solution:

	def minColour(self, N, M, mat):
		graph = {i: [] for i in range(1, N + 1)}
		for (i, j) in mat:
			graph[i].append(j)
		height = {}

		def calc_height(x):
			if x in height:
				return height[x]
			max_height = 1
			for y in graph[x]:
				hy = calc_height(y)
				if hy + 1 > max_height:
					max_height = hy + 1
			height[x] = max_height
			return max_height
		ans = 0
		for i in range(1, N + 1):
			if i not in height:
				calc_height(i)
			if height[i] > ans:
				ans = height[i]
		return ans


class Solution:

	def minColour(self, N, M, mat):
		adj = [[] for i in range(N + 1)]
		visit = [False] * (N + 1)
		d = [0] * (N + 1)
		for (k, v) in mat:
			adj[k].append(v)
		for i in range(1, N + 1):
			if not visit[i]:
				self.dfs(i, adj, visit, d)
		return max(d)

	def dfs(self, x, adj, visit, d):
		visit[x] = True
		leng = 0
		for i in adj[x]:
			if not visit[i]:
				self.dfs(i, adj, visit, d)
			leng = max(leng, d[i])
		d[x] = leng + 1


from collections import defaultdict

class Solution:

	def dfs(self, node, adj, dis):
		dis[node] = 0
		chain = 0
		for v in adj[node]:
			if dis[v] == -1:
				self.dfs(v, adj, dis)
			chain = max(chain, dis[v])
		dis[node] = chain + 1
		return dis[node]

	def minColour(self, N, M, mat):
		distance = [-1] * (N + 1)
		adj = defaultdict(list)
		for (u, v) in mat:
			adj[u].append(v)
		for node in range(1, N + 1):
			self.dfs(node, adj, distance)
		return max(distance)