There are a total of N tasks, labeled from 0 to N-1. Some tasks may have prerequisites, for example to do task 0 you have to first complete task 1, which is expressed as a pair: [0, 1]
Given the total number of tasks N and a list of prerequisite pairs P, find if it is possible to finish all tasks.
Example 1:
Input: 
N = 4, P = 3
prerequisites = {{1,0},{2,1},{3,2}}
Output:
Yes
Explanation:
To do task 1 you should have completed
task 0, and to do task 2 you should 
have finished task 1, and to do task 3 you 
should have finished task 2. So it is possible.
Example 2:
Input:
N = 2, P = 2
prerequisites = {{1,0},{0,1}}
Output:
No
Explanation:
To do task 1 you should have completed
task 0, and to do task 0 you should
have finished task 1. So it is impossible.
Your task:
You don’t need to read input or print anything. Your task is to complete the function isPossible() which takes the integer N denoting the number of tasks, P denoting the number of prerequisite pairs and prerequisite as input parameters and returns true if it is possible to finish all tasks otherwise returns false. 
Expected Time Complexity: O(N + P)
Expected Auxiliary Space: O(N + P)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ P ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def isPossible(self,N,prerequisites):
        #code here
    

Solutions:
from queue import Queue

class Solution:

	def isPossible(self, N, prerequisites):
		V = N
		adj = [[] for i in range(V)]
		for (edge, vertex) in prerequisites:
			adj[vertex].append(edge)
		visited = 0
		indegree = [0] * V
		i = 0
		for i in range(V):
			for j in range(len(adj[i])):
				indegree[adj[i][j]] += 1
		q = Queue()
		for i in range(V):
			if indegree[i] == 0:
				q.put(i)
		while q.empty() == False:
			var = q.get()
			visited += 1
			for i in range(len(adj[var])):
				indegree[adj[var][i]] -= 1
				if indegree[adj[var][i]] == 0:
					q.put(adj[var][i])
		if visited != V:
			return 0
		return 1


class Solution:

	def isPossible(self, N, prerequisites):
		adjList = self.adjListCreator(N, prerequisites)
		inDegree = self.inDegreeCreator(N, adjList)
		visited = [0 for i in range(0, N)]
		queue = []
		for i in range(0, N):
			if inDegree[i] == 0:
				queue.append(i)
		result = self.bfs(queue, adjList, inDegree)
		return len(result) == N

	def bfs(self, queue, adjList, inDegree):
		result = []
		while queue:
			currNode = queue.pop(0)
			result.append(currNode)
			for neighbour in adjList[currNode]:
				inDegree[neighbour] -= 1
				if inDegree[neighbour] == 0:
					queue.append(neighbour)
		return result

	def inDegreeCreator(self, n, adjList):
		indegree = [0 for i in range(0, n)]
		for neighbours in adjList.values():
			for node in neighbours:
				indegree[node] += 1
		return indegree

	def adjListCreator(self, n, edges):
		adjList = {i: [] for i in range(0, n)}
		for edge in edges:
			(start, end) = edge
			adjList[start].append(end)
		return adjList


class Solution:

	def isPossible(self, V, prerequisites):
		adj = []
		for i in range(V):
			adj.append([])
		for i in prerequisites:
			adj[i[1]].append(i[0])
		indegree = [0] * V
		queue = []
		stack = []
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop(0)
			stack.append(x)
			for i in adj[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		if len(stack) == V:
			return True
		return False


import sys
sys.setrecursionlimit(10000)

def dfs(node):
	if cycle[node] == 1:
		return True
	elif vis[node] == 1:
		return
	else:
		vis[node] = 1
		cycle[node] = 1
		for i in adj[node]:
			if dfs(i):
				return True
		cycle[node] = 0
		return False

def iscycle(adj):
	for i in range(len(adj)):
		if vis[i] == 0:
			ans = dfs(i)
			if ans:
				return ans
	return False

class Solution:

	def isPossible(self, N, prerequisites):
		global vis
		global cycle
		global adj
		vis = [0 for i in range(N)]
		cycle = [0 for i in range(N)]
		adj = [[] for i in range(N)]
		for (x, y) in prerequisites:
			adj[x].append(y)
		return not iscycle(adj)


def make_graph(graph, N, prereq):
	for p in prereq:
		graph[p[1]].add(p[0])

def dfs_cycle(graph, i, onpath, vis):
	if vis[i]:
		return 0
	onpath[i] = 1
	vis[i] = 1
	for neigh in graph[i]:
		if onpath[neigh] or dfs_cycle(graph, neigh, onpath, vis):
			return 1
	onpath[i] = 0
	return 0

class Solution:

	def isPossible(self, N, prereq):
		graph = []
		for i in range(N):
			graph.append(set())
		make_graph(graph, N, prereq)
		vis = [0] * N
		onpath = [0] * N
		for i in range(N):
			if vis[i] == 0 and dfs_cycle(graph, i, onpath, vis):
				return False
		return True


class Solution:

	def isPossible(self, N, prerequisites):
		indegree = [0] * N
		adj_list = [[] for _ in range(N)]
		for (dependent, independent) in prerequisites:
			indegree[dependent] += 1
			adj_list[independent].append(dependent)
		zero_degree = []
		nodes = 0
		for i in range(N):
			if indegree[i] == 0:
				zero_degree.append(i)
				nodes += 1
		if not zero_degree:
			return False
		while zero_degree:
			node = zero_degree.pop(0)
			for adj in adj_list[node]:
				indegree[adj] -= 1
				if indegree[adj] == 0:
					zero_degree.append(adj)
					nodes += 1
		if nodes == N:
			return True
		return False


from collections import defaultdict
import sys

class Solution:

	def isPossible(self, N, edges):

		def dfs(node):
			if node in visited:
				return
			if node in cycle:
				output.append(False)
				visited.add(node)
				return
			cycle.add(node)
			if node in adj:
				for item in adj[node]:
					dfs(item)
			visited.add(node)
		sys.setrecursionlimit(10000)
		adj = defaultdict(list)
		for (i, j) in edges:
			adj[i].append(j)
		visited = set()
		cycle = set()
		output = [True]
		for node in adj:
			dfs(node)
			if output[-1] == False:
				return False
		return True


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj_list = defaultdict(list)
		for (x, y) in prerequisites:
			adj_list[y].append(x)
		visit = [False] * N
		dfsvisit = [False] * N

		def dfs(node):
			visit[node] = True
			dfsvisit[node] = True
			for x in adj_list[node]:
				if not visit[x]:
					if dfs(x):
						return True
				elif dfsvisit[x]:
					return True
			dfsvisit[node] = False
			return False
		for i in range(N):
			if not visit[i]:
				if dfs(i):
					return False
		return True


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isPossible(self, n, prerequisites):
		graph = [[] for i in range(n)]
		for i in prerequisites:
			graph[i[0]].append(i[1])

		def dfs(sv):
			visited.add(sv)
			call.add(sv)
			for des in graph[sv]:
				if des not in visited:
					if not dfs(des):
						return False
				elif des in call:
					return False
			call.remove(sv)
			return True
		visited = set()
		call = set()
		for i in range(n):
			if i not in visited:
				if not dfs(i):
					return False
		return True


from queue import Queue

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for it in prerequisites:
			adj[it[0]].append(it[1])
		indegree = [0] * N
		for node in range(N):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		q = Queue()
		for node in range(N):
			if indegree[node] == 0:
				q.put(node)
		topo = []
		while not q.empty():
			node = q.get()
			topo.append(node)
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					q.put(adjNode)
		if len(topo) == N:
			return True
		else:
			return False


import collections

class Solution:

	def isPossible(self, N, prerequisites):
		V = N
		adj = [[] for i in range(V)]
		for (x, y) in prerequisites:
			adj[y].append(x)
		indegree = [0] * V
		for i in range(V):
			for ngb in adj[i]:
				indegree[ngb] += 1
		q = collections.deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for ngb in adj[node]:
				indegree[ngb] -= 1
				if indegree[ngb] == 0:
					q.append(ngb)
		if len(topo) == V:
			return True
		return False


from collections import deque

def make_graph(prerequisites):
	graph = {}
	indegree = {}
	for i in prerequisites:
		(dest, src) = i
		if src not in graph:
			graph[src] = [dest]
		else:
			graph[src].append(dest)
		if dest in indegree:
			indegree[dest] += 1
		else:
			indegree[dest] = 1
	return (graph, indegree)

class Solution:

	def isPossible(self, N, prerequisites):
		q = deque()
		count = 0
		(graph, indegree) = make_graph(prerequisites)
		for i in range(N):
			if i not in indegree or indegree[i] == 0:
				q.append(i)
				indegree[i] = -1
				count += 1
		while q:
			temp = q.popleft()
			if temp in graph:
				for k in graph[temp]:
					indegree[k] -= 1
					if indegree[k] == 0:
						q.append(k)
						count += 1
		if count == N:
			return True
		else:
			return False


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		graph = {i: [] for i in range(N)}
		for (v, u) in prerequisites:
			graph[u].append(v)

		def dfs(node):
			visited[node] = 1
			dfsvisit[node] = 1
			for nei in graph[node]:
				if not visited[nei]:
					if dfs(nei):
						return True
				elif dfsvisit[nei]:
					return True
			dfsvisit[node] = 0
			return False
		visited = [0] * N
		dfsvisit = [0] * N
		for node in range(N):
			if not visited[node]:
				if dfs(node):
					return False
		return True


class Solution:

	def isPossible(self, N, prerequisites):
		from collections import deque
		q = deque()
		count = 0
		indegree = [0 for i in range(N)]
		adj = [[] for i in range(N)]
		for i in prerequisites:
			indegree[i[0]] += 1
			adj[i[1]].append(i[0])
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
				count += 1
		while len(q) > 0:
			node = q.popleft()
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
					count += 1
		return count == N


from collections import defaultdict as dq

class Solution:

	def topoSort(self, n, arr):
		q = []
		ind = [0] * n
		for i in range(n):
			for j in arr[i]:
				ind[j] += 1
		for i in range(n):
			if ind[i] == 0:
				q.append(i)
		ptr = 0
		while ptr < len(q):
			for j in arr[q[ptr]]:
				ind[j] -= 1
				if ind[j] == 0:
					q.append(j)
			ptr += 1
		return q

	def isCyclic(self, n, grid):
		if len(self.topoSort(n, grid)) == n:
			return 1
		return 0

	def isPossible(self, n, prerequisites):
		arr = dq(list)
		for i in prerequisites:
			arr[i[1]].append(i[0])
		return self.isCyclic(n, arr)


from queue import Queue
from typing import List

class Solution:

	@staticmethod
	def in_degree_nodes(adjacency_list: List[List[int]], vertices: int) -> List[int]:
		in_degree_arr = [0 for _ in range(vertices)]
		for element in adjacency_list:
			for node in element:
				in_degree_arr[node] += 1
		return in_degree_arr

	@staticmethod
	def __kahn_algorithm__(adjacency_list: List[List[int]], ans: List[int], in_degree_arr: List[int]):
		q = Queue()
		for index in range(len(in_degree_arr)):
			if in_degree_arr[index] == 0:
				q.put(index)
		while not q.empty():
			node = q.get()
			ans.append(node)
			for ele in adjacency_list[node]:
				in_degree_arr[ele] -= 1
				if in_degree_arr[ele] == 0:
					q.put(ele)

	def topo_sort(self, adjacent: List[List[int]], vertices: int):
		in_degree_arr = self.in_degree_nodes(adjacent, vertices)
		ans = []
		self.__kahn_algorithm__(adjacent, ans, in_degree_arr)
		return len(ans) == vertices

	def isPossible(self, n, pre):
		adjacency_list = [[] for _ in range(n)]
		for (node1, node2) in pre:
			adjacency_list[node2].append(node1)
		return self.topo_sort(adjacency_list, n)


from collections import deque, defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		for (u, v) in prerequisites:
			adj[u].append(v)
		indegree = [0] * N
		for i in range(N):
			for node in adj[i]:
				indegree[node] += 1
		q = deque()
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		res = 0
		while q:
			node = q.popleft()
			res += 1
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		if res == N:
			return True
		return False


from collections import deque

class Solution:

	def isPossible(self, n, prerequisites):
		adj = [[] for i in range(n)]
		for courses in prerequisites:
			adj[courses[0]].append(courses[1])
		q = deque()
		inDegree = [0] * n
		for i in range(n):
			for j in adj[i]:
				inDegree[j] += 1
		for i in range(n):
			if inDegree[i] == 0:
				q.append(i)
		ans = 0
		while q:
			node = q.popleft()
			ans += 1
			for it in adj[node]:
				inDegree[it] -= 1
				if inDegree[it] == 0:
					q.append(it)
		return True if ans == n else False


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		graph = defaultdict(list)
		for (v, u) in prerequisites:
			graph[u].append(v)
		visited = [0 for i in range(N)]
		onpath = [0 for i in range(N)]

		def iscycle(node):
			visited[node] = 1
			onpath[node] = 1
			for nei in graph[node]:
				if not visited[nei] and iscycle(nei):
					return True
				elif onpath[nei] == 1:
					return True
			onpath[node] = 0
			return False
		for node in range(N):
			if not visited[node]:
				if iscycle(node):
					return False
		return True


from collections import defaultdict

class Solution:

	def isPossible(self, V, prerequisites):
		adj = defaultdict(list)
		for (v, u) in prerequisites:
			adj[u].append(v)

		def dfs(node, visited, currdfs):
			visited.add(node)
			currdfs.add(node)
			for neighbour in adj[node]:
				if neighbour not in visited:
					if dfs(neighbour, visited, currdfs):
						return True
				elif neighbour in currdfs:
					return True
			currdfs.remove(node)
			return False
		visited = set()
		currdfs = set()
		for node in range(V):
			if node not in visited:
				if dfs(node, visited, currdfs):
					return False
		return True


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for i in prerequisites:
			adj[i[0]].append(i[1])
		v = len(adj)
		q = deque()
		stack = []
		indegree = [0] * v
		for i in range(v):
			for ver in adj[i]:
				indegree[ver] += 1
		for i in range(v):
			if indegree[i] == 0:
				q.append(i)
				stack.append(i)
		while q:
			node = q.popleft()
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
					stack.append(i)
		if len(stack) == N:
			return True
		return False


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for ele in prerequisites:
			adj[ele[0]].append(ele[1])
		indegree = [0] * N
		for lst in adj:
			for i in lst:
				indegree[i] += 1
		stack = []
		for i in range(N):
			if indegree[i] == 0:
				stack.append(i)
		result = []
		while stack:
			s = stack.pop(0)
			result.append(s)
			for i in adj[s]:
				indegree[i] -= 1
				if indegree[i] == 0:
					stack.append(i)
		return len(result) == N


class Solution:

	def isPossible(self, N, prerequisites):
		V = N
		adj = {i: [] for i in range(V)}
		for i in prerequisites:
			if i[0] not in adj:
				adj[i[0]] = []
			adj[i[0]].append(i[1])
		indegree = [0 for i in range(V)]
		for i in range(V):
			for node in adj[i]:
				indegree[node] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		topo = []
		while len(queue):
			node = queue.pop(-1)
			topo.append(node)
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		return len(topo) == V


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for _ in range(N)]
		count = [0] * N
		for i in prerequisites:
			adj[i[1]].append(i[0])
			count[i[0]] = count[i[0]] + 1
		q = []
		for i in range(len(count)):
			if count[i] == 0:
				q.append(i)
		res = 0
		while q:
			x = q.pop(0)
			res = res + 1
			for i in adj[x]:
				count[i] = count[i] - 1
				if count[i] == 0:
					q.append(i)
		return res == N


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for elem in prerequisites:
			adj[elem[0]].append(elem[1])
		indegree = [0 for i in range(N)]
		for e in adj:
			for item in e:
				indegree[item] += 1
		queue = []
		for i in range(N):
			if indegree[i] == 0:
				queue.append(i)
		count = 0
		while len(queue) > 0:
			ele = queue.pop(0)
			count += 1
			for x in adj[ele]:
				indegree[x] -= 1
				if indegree[x] == 0:
					queue.append(x)
		if N == count:
			return True
		return False


from collections import defaultdict, deque

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for (i, j) in prerequisites:
			adj[i].append(j)
		indegree = [0] * N
		for (i, j) in prerequisites:
			indegree[j] += 1
		q = deque()
		count = 0
		for d in range(N):
			if indegree[d] == 0:
				q.append(d)
				count += 1
		while q:
			v = q.popleft()
			for item in adj[v]:
				indegree[item] -= 1
				if indegree[item] == 0:
					q.append(item)
					count += 1
		return count == N


class Solution:

	def isPossible(self, N, prerequisites):
		from collections import deque
		adj = [[] for i in range(N)]
		for i in prerequisites:
			adj[i[0]].append(i[1])
		indegree = [0] * N
		q = deque()
		for i in range(N):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return True if len(topo) == N else False


class Solution:

	def isPossible(self, n, prerequisites):
		adj = [[] for i in range(n)]
		for i in range(len(prerequisites)):
			adj[prerequisites[i][0]].append(prerequisites[i][1])
		indegree = [0] * n
		for i in range(n):
			for it in adj[i]:
				indegree[it] += 1
		ans = []
		q = []
		for i in range(n):
			if indegree[i] == 0:
				q.append(i)
		while q:
			a = q.pop(0)
			ans.append(a)
			for it in adj[a]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		return len(ans) == n


from collections import deque
from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		for it in prerequisites:
			(u, v) = it
			adj[u].append(v)
		indegree = [0] * N
		for i in range(N):
			for it in adj[i]:
				indegree[it] += 1
		q = deque()
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			ele = q.popleft()
			topo.append(ele)
			for it in adj[ele]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		if len(topo) == N:
			return True
		return False


class Solution:

	def isPossible(self, numCourses, prerequisites):
		adj = [[] for i in range(numCourses)]
		queue = []
		cnt = 0
		indeg = [0 for i in range(numCourses)]
		for i in prerequisites:
			adj[i[1]].append(i[0])
			indeg[i[0]] += 1
		for i in range(numCourses):
			if indeg[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop(0)
			cnt += 1
			for node in adj[x]:
				indeg[node] -= 1
				if indeg[node] == 0:
					queue.append(node)
		return cnt == numCourses


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		indeg = [0] * N
		q = []
		topo = []
		for (src, dest) in prerequisites:
			adj[src].append(dest)
			indeg[dest] += 1
		for i in range(N):
			if indeg[i] == 0:
				q.append(i)
		while q:
			node = q.pop(0)
			topo.append(node)
			for it in adj[node]:
				indeg[it] -= 1
				if indeg[it] == 0:
					q.append(it)
		for i in range(N):
			if indeg[i] != 0:
				return False
		return True


from typing import List, Tuple
from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		V = N
		adj = [[] for _ in range(V)]
		for i in prerequisites:
			adj[i[0]].append(i[1])
		indegree = [0] * V
		for i in range(V):
			for it in adj[i]:
				indegree[it] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		return len(topo) == N


class Solution:

	def isPossible(self, N, prerequisites):
		indeg = [0] * N
		adj = [[] for i in range(N)]
		for (src, dest) in prerequisites:
			adj[src].append(dest)
			indeg[dest] += 1
		queue = []
		for i in range(N):
			if indeg[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			a = queue.pop(0)
			ans.append(a)
			for i in adj[a]:
				indeg[i] -= 1
				if indeg[i] == 0:
					queue.append(i)
		if len(ans) == N:
			return 1
		else:
			return 0


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		adj = []
		for i in range(N):
			row = []
			adj.append(row)
		for (u, v) in prerequisites:
			adj[v].append(u)
		indeg_arr = [0] * N
		vis = [0] * N
		for neigbour in adj:
			for node in neigbour:
				indeg_arr[node] += 1
		queue = deque()
		for i in range(N):
			if indeg_arr[i] == 0:
				queue.append(i)
		count = 0
		while len(queue) > 0:
			node = queue.popleft()
			count += 1
			for n_node in adj[node]:
				indeg_arr[n_node] -= 1
				if indeg_arr[n_node] == 0:
					queue.append(n_node)
		if count == N:
			return True
		else:
			return False


from collections import deque, defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		queue = deque()
		indegree = {}
		for (child, parent) in prerequisites:
			adj[parent].append(child)
		for i in range(N):
			indegree[i] = 0
		for i in range(N):
			for child in adj[i]:
				indegree[child] += 1
		for i in range(len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		cnt = 0
		while queue:
			node = queue.popleft()
			cnt += 1
			for child in adj[node]:
				indegree[child] -= 1
				if indegree[child] == 0:
					queue.append(child)
		if cnt == N:
			return True
		else:
			return False


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		indegree = [0 for i in range(N)]
		for i in prerequisites:
			adj[i[0]].append(i[1])
			indegree[i[1]] += 1
		q = []
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			x = q.pop(0)
			topo.append(x)
			for i in adj[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		if len(topo) != N:
			return False
		return True


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		for i in prerequisites:
			adj[i[0]] += [i[-1]]
		indegree = [0] * N
		for i in range(0, N):
			for j in adj[i]:
				indegree[j] += 1
		queue = []
		for i in range(0, N):
			if indegree[i] == 0:
				queue += [i]
		topo = []
		while queue:
			node = queue.pop(0)
			topo += [node]
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue += [i]
		if len(topo) == N:
			return 1
		return 0


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		for i in prerequisites:
			adj[i[0]].append(i[1])
		ind = [0] * N
		for i in range(N):
			for j in adj[i]:
				ind[j] += 1
		q = []
		for i in range(N):
			if ind[i] == 0:
				q.append(i)
		topo = []
		while q:
			temp = q.pop(0)
			topo.append(temp)
			for i in adj[temp]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		if len(topo) == N:
			return topo
		return []


from collections import deque

class Solution:

	def isPossible(self, N, l):
		adj = [[] for _ in range(N)]
		in_degree = [0] * N
		for (u, v) in l:
			adj[v].append(u)
			in_degree[u] += 1
		visited = 0
		q = deque([u for u in range(N) if in_degree[u] == 0])
		while q:
			node = q.popleft()
			visited += 1
			for v in adj[node]:
				in_degree[v] -= 1
				if in_degree[v] == 0:
					q.append(v)
		return visited == N


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		vis = [0] * N
		for i in prerequisites:
			adj[i[0]].append(i[1])
		for i in range(N):
			for j in adj[i]:
				vis[j] += 1
		q = []
		b = []
		for i in range(N):
			if vis[i] == 0:
				q.append(i)
		while q:
			s = q.pop(0)
			b.append(s)
			for i in adj[s]:
				vis[i] -= 1
				if vis[i] == 0:
					q.append(i)
		if len(b) == N:
			return True
		return False


from collections import defaultdict, deque

class Solution:

	def isPossible(self, V, prerequisites):
		adj = defaultdict(list)
		for (a, b) in prerequisites:
			adj[a].append(b)
		indegree = [0] * V
		for i in range(V):
			for node in adj[i]:
				indegree[node] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		topo = 0
		while q:
			node = q.popleft()
			topo += 1
			for neighbor in adj[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					q.append(neighbor)
		if topo == V:
			return True
		return False


from collections import deque

class Solution:

	def isPossible(self, N, pre):
		adj = [[] for i in range(N)]
		for it in pre:
			adj[it[0]].append(it[1])
		indegree = dict.fromkeys(range(N), 0)
		s = []
		for i in range(N):
			for it in adj[i]:
				indegree[it] += 1
		q = deque()
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		while len(q) > 0:
			node = q.popleft()
			s.append(node)
			for n in adj[node]:
				indegree[n] -= 1
				if indegree[n] == 0:
					q.append(n)
		if len(s) == N:
			return True
		return False


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		graph = [[] for _ in range(N)]
		for tasks in prerequisites:
			(pre, post) = tasks
			graph[pre].append(post)
		inDegree = [0 for _ in range(N)]
		queue = deque()
		for i in range(N):
			for node in graph[i]:
				inDegree[node] += 1
		for i in range(N):
			if inDegree[i] == 0:
				queue.append(i)
		topo = 0
		while queue:
			root = queue.popleft()
			topo += 1
			for node in graph[root]:
				inDegree[node] -= 1
				if inDegree[node] == 0:
					queue.append(node)
		return topo == N


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		graph = [[] for _ in range(N)]
		for temp in prerequisites:
			graph[temp[0]].append(temp[1])
		visited = [0 for _ in range(N)]
		for i in range(N):
			for u in graph[i]:
				visited[u] += 1
		queue = deque([])
		for i in range(N):
			if visited[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for u in graph[node]:
				visited[u] -= 1
				if visited[u] == 0:
					queue.append(u)
		if len(ans) == N:
			return True
		else:
			return False


from collections import *

class Solution:

	def isPossible(self, N, prerequisites):
		graph = defaultdict(list)
		for (i, j) in prerequisites:
			graph[i].append(j)
		indeg = [0] * N
		for i in range(N):
			for node in graph[i]:
				indeg[node] += 1
		qu = deque()
		for i in range(N):
			if indeg[i] == 0:
				qu.append(i)
		ans = 0
		while qu:
			curr = qu.popleft()
			ans += 1
			for nei in graph[curr]:
				indeg[nei] -= 1
				if indeg[nei] == 0:
					qu.append(nei)
		return ans == N


from queue import Queue

class Solution:

	def isPossible(self, V, prerequisites):
		adj = [[] for i in range(V)]
		for x in prerequisites:
			adj[x[0]].append(x[1])
		q = Queue()
		ind = [0 for i in range(V)]
		for i in range(V):
			for x in adj[i]:
				ind[x] += 1
		for i in range(V):
			if ind[i] == 0:
				q.put(i)
		top = []
		while q.qsize() != 0:
			node = q.get()
			top.append(node)
			for x in adj[node]:
				ind[x] -= 1
				if ind[x] == 0:
					q.put(x)
		if len(top) == V:
			return True
		else:
			return False


class Solution:

	def isPossible(self, n, prerequisites):
		adj = [[] for i in range(n)]
		for (i, j) in prerequisites:
			adj[i].append(j)
		visited = [False] * n
		onstack = [False] * n
		stack = []
		for i in range(n):
			if visited[i]:
				continue
			stack.append(i)
			while len(stack):
				v = stack[-1]
				if not visited[v]:
					visited[v] = True
					onstack[v] = True
				else:
					onstack[v] = False
					stack.pop()
				for w in adj[v]:
					if not visited[w]:
						stack.append(w)
					elif onstack[w]:
						return False
		return True


class Solution:

	def isPossible(self, N, pre):
		adj = [[] for i in range(N)]
		for pair in pre:
			adj[pair[0]].append(pair[1])
		indegree = [0 for i in range(N)]
		for i in range(N):
			for it in adj[i]:
				indegree[it] += 1
		q = []
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.pop(0)
			topo.append(node)
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		if len(topo) == N:
			return True
		return False


class Solution:

	def isPossible(self, N, prerequisites):
		from collections import defaultdict
		G = defaultdict(list)
		indeg = [0] * N
		for (u, v) in prerequisites:
			G[v].append(u)
			indeg[u] += 1
		q = []
		for i in range(N):
			if indeg[i] == 0:
				q.append(i)
		kunt = 0
		while q:
			top = q.pop(0)
			kunt += 1
			for adjNode in G[top]:
				indeg[adjNode] -= 1
				if indeg[adjNode] == 0:
					q.append(adjNode)
		return kunt == N


class Solution:

	def isPossible(self, V, prerequisites):
		adj = [[] for i in range(V)]
		for pair in prerequisites:
			adj[pair[0]].append(pair[1])
		topo = []
		que = []
		indegree = [0] * V
		for ls in adj:
			for val in ls:
				indegree[val] += 1
		for i in range(V):
			if indegree[i] == 0:
				que.append(i)
		while len(que) > 0:
			node = que.pop(0)
			topo.append(node)
			for nd in adj[node]:
				indegree[nd] -= 1
				if indegree[nd] == 0:
					que.append(nd)
		return len(topo) == V


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for x in range(N)]
		indegree = [0 for x in range(N)]
		(nodes_with_0, res) = ([], [])
		for task in prerequisites:
			(after_task, before_task) = (task[0], task[1])
			adj[after_task].append(before_task)
			indegree[before_task] += 1
		for index in range(len(indegree)):
			if indegree[index] == 0:
				nodes_with_0.append(index)
		while len(nodes_with_0) != 0:
			node = nodes_with_0.pop()
			res.append(node)
			for neighbor in adj[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					nodes_with_0.append(neighbor)
		if len(res) == N:
			return True
		return False


class Solution:

	def isPossible(self, N, prerequisites):
		graph = [[] for _ in range(N)]
		for task in prerequisites:
			graph[task[1]].append(task[0])
		indegree = [0] * (N + 1)
		for node in range(N):
			for adjNode in graph[node]:
				indegree[adjNode] += 1
		queue = []
		for node in range(N):
			if indegree[node] == 0:
				queue.append(node)
		cnt = 0
		while queue:
			node = queue.pop(0)
			cnt += 1
			for adjNode in graph[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					queue.append(adjNode)
		if cnt != N:
			return False
		return True


from collections import defaultdict, deque

class Solution:

	def isPossible(self, n, edges):
		g = defaultdict(lambda : [])
		for (u, v) in edges:
			g[v].append(u)
		seen = [False] * n
		rec = [False] * n

		def dfs(u):
			seen[u] = True
			rec[u] = True
			for v in g[u]:
				if not seen[v]:
					if dfs(v):
						return True
				elif rec[v]:
					return True
			rec[u] = False
			return False
		for i in range(n):
			if not seen[i]:
				if dfs(i):
					return False
		return True


from collections import defaultdict, deque

class Solution:

	def isPossible(self, n, edges):
		g = defaultdict(lambda : [])
		deg = [0] * n
		for (u, v) in edges:
			g[u].append(v)
			deg[v] += 1
		q = deque([i for i in range(n) if deg[i] == 0])
		c = 0
		while q:
			u = q.popleft()
			c += 1
			for v in g[u]:
				deg[v] -= 1
				if deg[v] == 0:
					q.append(v)
		return c == n


class Solution:

	def isCycle(self, adj, source):
		self.visited[source] = True
		self.rec[source] = True
		for x in adj[source]:
			if self.visited[x] == False:
				if self.isCycle(adj, x) == True:
					return True
			elif self.rec[x] == True:
				return True
		self.rec[source] = False
		return False

	def isPossible(self, N, prerequisites):
		from collections import defaultdict
		adj = defaultdict(list)
		for x in prerequisites:
			adj[x[1]].append(x[0])
		self.visited = [False for i in range(N)]
		self.rec = [False for i in range(N)]
		for i in range(N):
			if self.visited[i] == False:
				if self.isCycle(adj, i) == True:
					return False
		return True


from collections import deque

def bfs(ind, depend):
	q = deque()
	cnt = 0
	for i in range(len(ind)):
		if ind[i] == 0:
			q.append(i)
	while len(q):
		cnt += 1
		val = q.popleft()
		for i in depend[val]:
			ind[i] -= 1
			if ind[i] == 0:
				q.append(i)
	return cnt

class Solution:

	def isPossible(self, N, pre):
		adj = [[] for i in range(N)]
		depend = [[] for i in range(N)]
		lp = len(pre)
		for i in range(lp):
			adj[pre[i][0]].append(pre[i][1])
			depend[pre[i][1]].append(pre[i][0])
		ind = [0] * N
		for i in range(N):
			ind[i] = len(adj[i])
		if bfs(ind, depend) == N:
			return True
		return False


def dfs(node, nodes, adjList, color):
	color[node] = 'g'
	for nextNode in adjList[node]:
		if color[nextNode] == 'w':
			if dfs(nextNode, nodes, adjList, color):
				return 1
		elif color[nextNode] == 'g':
			return 1
	color[node] = 'b'
	return 0

class Solution:

	def isPossible(self, nodes, prerequisites):
		adjList = [[] for node in range(nodes)]
		color = ['w' for node in range(nodes)]
		for (src, dest) in prerequisites:
			adjList[dest].append(src)
		for node in range(nodes):
			if color[node] == 'w':
				if dfs(node, nodes, adjList, color):
					return False
		return True


class Solution:

	def isPossible(self, N, prerequisites):
		inDegree = [0] * N
		graph = [[] for i in range(N)]
		for (task0, task1) in prerequisites:
			graph[task1].append(task0)
			inDegree[task0] += 1
		q = []
		count = 0
		for i in range(N):
			if inDegree[i] == 0:
				q.append(i)
		while q:
			node = q.pop(0)
			count += 1
			for it in graph[node]:
				inDegree[it] -= 1
				if inDegree[it] == 0:
					q.append(it)
		if count == N:
			return True
		return False


class Solution:

	def isPossible(self, N, prerequisites):
		V = N
		vis = [0] * V
		ind = [0] * N
		from collections import defaultdict as dd
		adj = dd(list)
		for (a, b) in prerequisites:
			adj[a].append(b)
			ind[b] += 1
		q = []
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		while q:
			n = q.pop(0)
			for i in adj[n]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		for i in ind:
			if i > 0:
				return False
		return True


import collections

class Solution:

	def isPossible(self, N, preq):
		adj = [[] for i in range(N)]
		for eachPair in preq:
			adj[eachPair[0]].append(eachPair[1])
		inDegree = [0 for i in range(N)]
		for eachArr in adj:
			for eachNode in eachArr:
				inDegree[eachNode] = inDegree[eachNode] + 1
		deque = collections.deque()
		for i in range(len(inDegree)):
			if inDegree[i] == 0:
				deque.append(i)
		zeroCount = 0
		while len(deque) > 0:
			for i in range(len(deque)):
				zeroCount += 1
				popVal = deque.popleft()
				for eachNode in adj[popVal]:
					inDegree[eachNode] = inDegree[eachNode] - 1
					if inDegree[eachNode] == 0:
						deque.append(eachNode)
		if zeroCount == len(inDegree):
			return True
		return False


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		g = defaultdict(list)
		indegree = [0] * N
		for (u, v) in prerequisites:
			indegree[u] += 1
			g[v].append(u)
		q = []
		courses = 0
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
				courses += 1
		while q:
			temp = []
			for node in q:
				for neighbor in g[node]:
					indegree[neighbor] -= 1
					if indegree[neighbor] == 0:
						temp.append(neighbor)
						courses += 1
			q = temp
		return courses == N


from collections import defaultdict
from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		d = defaultdict(list)
		for i in prerequisites:
			d[i[1]].append(i[0])
		indeg = [0] * N
		for i in range(N):
			for j in d[i]:
				indeg[j] += 1
		q = deque()
		for i in range(N):
			if indeg[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for i in d[node]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		return len(topo) == N


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		adj = {}
		for u in range(N):
			adj[u] = []
		indegree = [0] * N
		for (u, v) in prerequisites:
			indegree[u] += 1
			adj[v].append(u)
		Q = deque()
		for u in range(N):
			if indegree[u] == 0:
				Q.append(u)
		visited = [False] * N
		while Q:
			u = Q.popleft()
			visited[u] = True
			for v in adj[u]:
				indegree[v] -= 1
				if indegree[v] == 0:
					Q.append(v)
		for i in range(N):
			if not visited[i]:
				return False
		return True


import collections

class Solution:

	def isPossible(self, V, prerequisites):
		graph = [[] for _ in range(V)]
		for edge in prerequisites:
			graph[edge[0]].append(edge[1])
		indegree = V * [0]
		queue = collections.deque()
		topo = []
		for node in range(V):
			for neighbor in graph[node]:
				indegree[neighbor] += 1
		for node in range(V):
			if indegree[node] == 0:
				queue.append(node)
		while queue:
			node = queue.popleft()
			topo.append(node)
			for neighbor in graph[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)
		return len(topo) == V


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		indegree = [0] * N
		queue = deque()
		adj = [[] for j in range(N)]
		for tasks in prerequisites:
			(second_task, first_task) = tasks
			adj[first_task].append(second_task)
		for i in range(N):
			for elements in adj[i]:
				indegree[elements] += 1
		for (index, element) in enumerate(indegree):
			if element == 0:
				queue.append(index)
		topo_sort = []
		while queue:
			popped_node = queue.popleft()
			topo_sort.append(popped_node)
			for neighbors in adj[popped_node]:
				indegree[neighbors] -= 1
				if indegree[neighbors] == 0:
					queue.append(neighbors)
		return True if len(topo_sort) == N else False


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		indeg = [0] * N
		adj = [[] for i in range(N)]
		for (src, dest) in prerequisites:
			adj[src].append(dest)
			indeg[dest] += 1
		q = deque([])
		for node in range(N):
			if indeg[node] == 0:
				q.append(node)
		while q:
			node = q.popleft()
			for nei in adj[node]:
				indeg[nei] -= 1
				if indeg[nei] == 0:
					q.append(nei)
		for i in range(N):
			if indeg[i] != 0:
				return False
		return True


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		tasks_completed = 0
		indegree = [0 for _ in range(N)]
		adj = [[] for _ in range(N)]
		for (task1, task2) in prerequisites:
			adj[task1].append(task2)
			indegree[task2] += 1
		q = deque()
		for index in range(N):
			if indegree[index] == 0:
				q.append(index)
		while q:
			current = q.popleft()
			tasks_completed += 1
			for neighbor in adj[current]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					q.append(neighbor)
		return tasks_completed == N


from queue import Queue

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		indegree = [0 for i in range(N)]
		for ele in prerequisites:
			adj[ele[0]].append(ele[1])
		for ele in adj:
			for i in ele:
				indegree[i] += 1
		q = Queue()
		for i in range(N):
			if indegree[i] == 0:
				q.put(i)
		ans = 0
		while not q.empty():
			ele = q.get()
			ans += 1
			for i in adj[ele]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.put(i)
		if ans == N:
			return True
		return False


from collections import deque

class Solution:

	def isPossible(self, N, prerequisites):
		graph = []
		for i in range(N):
			graph.append(list())
		for edge in prerequisites:
			graph[edge[0]].append(edge[1])
		indegree = [0] * N
		for i in range(N):
			for it in graph[i]:
				indegree[it] += 1
		queue = deque()
		for i in range(N):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for i in graph[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		if len(ans) == N:
			return True
		else:
			return False


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		for (src, dest) in prerequisites:
			adj[src].append(dest)
		indegree = [0 for i in range(N)]
		for i in range(N):
			for it in adj[i]:
				indegree[it] += 1
		q = []
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.pop(0)
			topo.append(node)
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		if len(topo) == N:
			return 1
		return 0


def func(pos, gr, visted, path):
	visted.add(pos)
	path.add(pos)
	for i in gr[pos]:
		if i not in visted:
			if func(i, gr, visted, path):
				return True
		elif i in path:
			return True
	path.remove(pos)
	return False

class Solution:

	def isPossible(self, n, s):
		gr = [[] for i in range(n)]
		for (i, j) in s:
			gr[j].append(i)
		path = set()
		visted = set()
		for i in range(n):
			if i not in visted:
				if func(i, gr, visted, path):
					return False
		return True


class Solution:

	def dfs(self, index, N, adjList, vis):
		vis[index] = 2
		for node in adjList[index]:
			if vis[node] == 0:
				if self.dfs(node, N, adjList, vis):
					return True
			elif vis[node] == 2:
				return True
		vis[index] = 1
		return False

	def detectCycle(self, N, adjList):
		vis = [0] * N
		for i in range(N):
			if vis[i] == 0:
				if self.dfs(i, N, adjList, vis):
					return True
		return False

	def isPossible(self, N, prerequisites):
		adjList = {}
		for i in range(N):
			adjList[i] = []
		for (task, prereq) in prerequisites:
			adjList[prereq].append(task)
		return not self.detectCycle(N, adjList)


from collections import defaultdict

class Solution:

	def isPossible(self, N, pre):
		adj = defaultdict(list)
		for (u, v) in pre:
			adj[v].append(u)
		visited = [0] * N
		dfs_visited = [0] * N
		for i in range(N):
			if not visited[i]:
				if not visited[i] and self.check_Cycledfs(i, visited, dfs_visited, adj):
					return False
		return True

	def check_Cycledfs(self, node, visited, dfs_visited, adj):
		visited[node] = True
		dfs_visited[node] = True
		for i in adj[node]:
			if not visited[i]:
				cycle = self.check_Cycledfs(i, visited, dfs_visited, adj)
				if cycle:
					return True
			elif dfs_visited[i] == True:
				return True
		dfs_visited[node] = False
		return False


from collections import defaultdict

class Solution:

	def isPossible(self, N, prerequisites):
		adj = defaultdict(list)
		indegree = [0] * N
		q = []
		P = len(prerequisites)
		for i in range(P):
			adj[prerequisites[i][0]].append(prerequisites[i][1])
		for i in range(N):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			temp = q.pop(0)
			ans.append(temp)
			for i in adj[temp]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		if len(ans) == N:
			return True
		return False


from queue import Queue

class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for _ in range(N)]
		for (neighbour, parent) in prerequisites:
			adj[parent].append(neighbour)
		(queue, order) = (Queue(), [])
		indegrees = [0] * N
		for neighbours in adj:
			for node in neighbours:
				indegrees[node] += 1
		for node in range(N):
			if indegrees[node] == 0:
				queue.put(node)
		while not queue.empty():
			node = queue.get()
			order.append(node)
			for neighbour in adj[node]:
				indegrees[neighbour] -= 1
				if indegrees[neighbour] == 0:
					queue.put(neighbour)
		return True if len(order) == N else False


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isPossible(self, N, pre):
		adj = [set() for i in range(N)]
		for i in pre:
			adj[i[0]].add(i[1])

		def dfs(s):
			visit[s] = 1
			visit[s] = 2
			for ele in adj[s]:
				if ele not in visit:
					if dfs(ele) == True:
						return True
				elif visit[ele] == 2:
					return True
			visit[s] = 1
			return False
		visit = {}
		for i in range(N):
			if i not in visit:
				if dfs(i) == True:
					return False
		return True


class Solution:

	def isPossible(self, N, prerequisites):
		adj = [[] for i in range(N)]
		queue = []
		result = []
		for i in prerequisites:
			adj[i[0]].append(i[1])
		inBranch = [0 for i in range(N)]
		for i in adj:
			for j in i:
				inBranch[j] += 1
		for i in range(N):
			if inBranch[i] == 0:
				queue.append(i)
		while len(queue) > 0:
			temp = queue.pop(0)
			result.append(temp)
			for i in adj[temp]:
				inBranch[i] -= 1
				if inBranch[i] == 0:
					queue.append(i)
		return 1 if len(result) == N else 0


from collections import defaultdict

class Solution:

	def isPossible(self, N, P):
		graph = defaultdict(list)
		for (a, b) in P:
			graph[b].append(a)
		(visited, tracker) = ([False] * N, [False] * N)

		def DFS(node):
			(visited[node], tracker[node]) = (True, True)
			for neighbour in graph[node]:
				if tracker[neighbour]:
					return True
				if not visited[neighbour] and DFS(neighbour):
					return True
			tracker[node] = False
			return False
		return all((not DFS(i) for i in range(N) if not visited[i]))


class Solution:

	def isPossible(self, N, prerequisites):
		(n, tasks) = (N, prerequisites)
		in_nodes = {i: [] for i in range(n)}
		out_deg = {i: 0 for i in range(n)}
		res = []
		for (u, v) in tasks:
			in_nodes[v].append(u)
			out_deg[u] += 1
		q = [i for i in range(n) if not out_deg[i]]
		while q:
			node = q.pop(0)
			res.append(node)
			for nei in in_nodes[node]:
				out_deg[nei] -= 1
				if not out_deg[nei]:
					q.append(nei)
		return len(res) == n


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, adj, vis):
		vis[node] = 2
		for i in adj[node]:
			if vis[i] == 0:
				if self.dfs(i, adj, vis):
					return True
			elif vis[i] == 2:
				return True
		vis[node] = 1
		return False

	def isPossible(self, N, p):
		vis = [0] * N
		adj = [[] for i in range(N)]
		for (i, j) in p:
			adj[i].append(j)
		for i in range(N):
			if vis[i] == 0:
				if self.dfs(i, adj, vis):
					return False
		return True


class Solution:

	def dfscycle(self, i, adj, visited, rec):
		rec[i] = True
		visited[i] = True
		for u in adj[i]:
			if not visited[u] and self.dfscycle(u, adj, visited, rec):
				return True
			elif rec[u]:
				return True
		rec[i] = False
		return False

	def isPossible(self, N, prerequisites):
		graph = []
		for i in range(N):
			graph.append([])
		for (i, j) in prerequisites:
			graph[j].append(i)
		visited = [False] * N
		rec = [False] * N
		for i in range(N):
			if not visited[i]:
				if self.dfscycle(i, graph, visited, rec):
					return False
		return True


class Solution:

	def isPossible(self, N, prerequisites):
		stack = []
		adj = [[] for _ in range(N)]
		ind_degree = [0] * N
		for item in prerequisites:
			adj[item[0]].append(item[1])
		for (i, item) in enumerate(adj):
			if item:
				for j in item:
					ind_degree[j] += 1
		for (i, item) in enumerate(ind_degree):
			if item == 0:
				stack.append(i)
		ans = []
		while stack:
			node = stack.pop(0)
			ans.append(node)
			for item in adj[node]:
				ind_degree[item] -= 1
				if ind_degree[item] == 0:
					stack.append(item)
		if len(ans) == N:
			return True
		return False