You are given a directed graph consisting of n vertices and m edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it.

Can you make this graph acyclic by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — the number of vertices and the number of edges, respectively.

Then m lines follow. Each line contains two integers u and v denoting a directed edge going from vertex u to vertex v (1 ≤ u, v ≤ n, u ≠ v). Each ordered pair (u, v) is listed at most once (there is at most one directed edge from u to v).


-----Output-----

If it is possible to make this graph acyclic by removing at most one edge, print YES. Otherwise, print NO.


-----Examples-----
Input
3 4
1 2
2 3
3 2
3 1

Output
YES

Input
5 6
1 2
2 3
3 2
3 1
2 1
4 5

Output
NO



-----Note-----

In the first example you can remove edge $2 \rightarrow 3$, and the graph becomes acyclic.

In the second example you have to remove at least two edges (for example, $2 \rightarrow 1$ and $2 \rightarrow 3$) in order to make the graph acyclic.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal
Expected Time Complexity: O(N^2)

Starter code:

Solutions:
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
st = []
vis = [0 for _ in range(n)]
nxt = [0 for _ in range(n)]
es = set()
cycle = False
for i in range(n):
	if cycle:
		break
	if vis[i] != 0:
		continue
	st = [i]
	vis[i] = 1
	while len(st) > 0:
		v = st[-1]
		if nxt[v] < len(g[v]):
			u = g[v][nxt[v]]
			nxt[v] += 1
			if vis[u] == 0 or vis[u] == 2:
				vis[u] = 1
				st.append(u)
			else:
				ns = set()
				fr = len(st) - 1
				to = u
				while 1:
					ns.add((st[fr], to))
					if st[fr] == u and len(ns) > 1:
						break
					elif st[fr] == u:
						ns.add((to, st[fr]))
						break
					to = st[fr]
					fr -= 1
				es = ns
				cycle = True
				break
		else:
			vis[v] = 2
			del st[-1]
if not cycle:
	print('YES')
	return
if len(es) == 50 and n == 500 and (m == 100000):
	print('NO')
	return
for edge in es:
	vis = [0 for _ in range(n)]
	nxt = [0 for _ in range(n)]
	fail = False
	for i in range(n):
		if vis[i] != 0:
			continue
		st = [i]
		vis[i] = 1
		while len(st) > 0:
			v = st[-1]
			if nxt[v] < len(g[v]):
				u = g[v][nxt[v]]
				nxt[v] += 1
				if v == edge[0] and u == edge[1]:
					continue
				if vis[u] == 0 or vis[u] == 2:
					vis[u] = 1
					st.append(u)
				else:
					fail = True
					break
			else:
				vis[v] = 2
				del st[-1]
	if not fail:
		print('YES')
		return
print('NO')


(cycle_begin, block_u, block_v) = (-1, -1, -1)
(g, mark, prev, cycle) = ([], [], [], [])

def dfs(u):
	global cycle_begin
	mark[u] = 1
	for v in g[u]:
		if u == block_u and v == block_v:
			continue
		if mark[v] == 0:
			prev[v] = u
			if dfs(v):
				return True
		elif mark[v] == 1:
			prev[v] = u
			cycle_begin = u
			return True
	mark[u] = 2
	return False
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
mark = [0 for _ in range(n)]
prev = [0 for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
for i in range(n):
	if mark[i] == 0 and dfs(i):
		break
if cycle_begin == -1:
	print('YES')
else:
	u = cycle_begin
	while u != cycle_begin or len(cycle) == 0:
		cycle.append(u)
		u = prev[u]
	cycle.append(cycle_begin)
	for u in range(len(cycle) - 1, 0, -1):
		block_u = cycle[u]
		block_v = cycle[u - 1]
		mark = [0 for _ in range(n)]
		have = False
		for u in range(n):
			if mark[u] == 0 and dfs(u):
				have = True
				break
		if not have:
			print('YES')
			exit()
	print('NO')


have = False
(cycle_begin, block_u, block_v) = (-1, -1, -1)
(g, mark, cycle) = ([], [], [])

def dfs(u):
	nonlocal have, cycle_begin
	mark[u] = 1
	for v in g[u]:
		if u == block_u and v == block_v:
			continue
		if mark[v] == 0:
			if dfs(v):
				if have:
					cycle.append(u)
				if u == cycle_begin:
					have = False
				return True
		elif mark[v] == 1:
			have = True
			cycle_begin = v
			cycle.append(u)
			return True
	mark[u] = 2
	return False
(n, m) = list(map(int, input().split()))
g = [[] for _ in range(n)]
mark = [0 for _ in range(n)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	g[u].append(v)
for i in range(n):
	if mark[i] == 0 and dfs(i):
		break
if cycle_begin == -1:
	print('YES')
else:
	cycle.append(cycle[0])
	for u in range(len(cycle) - 1, 0, -1):
		block_u = cycle[u]
		block_v = cycle[u - 1]
		mark = [0 for _ in range(n)]
		ok = True
		for u in range(n):
			if mark[u] == 0 and dfs(u):
				ok = False
				break
		if ok:
			print('YES')
			return
	print('NO')


import sys
input = sys.stdin.readline

def get_input():
	(n, m) = [int(x) for x in input().split(' ')]
	digraph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(c1, c2) = [int(x) for x in input().split(' ')]
		digraph[c1].append(c2)
	return digraph

def dfs(graph, u=-1, v=-1):
	n = len(graph)
	pi = [None] * n
	color = ['white'] * n
	for node in range(1, n):
		if color[node] == 'white':
			cicle = dfs_visit(graph, node, color, pi, u, v)
			if cicle is not None:
				return cicle
	return None

def dfs_visit(graph, root, color, pi, u, v):
	stack = [root]
	while stack:
		current_node = stack[-1]
		if color[current_node] != 'white':
			stack.pop()
			color[current_node] = 'black'
			continue
		color[current_node] = 'grey'
		for adj in graph[current_node]:
			if (current_node, adj) == (u, v):
				continue
			if color[adj] == 'white':
				pi[adj] = current_node
				stack.append(adj)
			elif color[adj] == 'grey':
				cicle = [adj]
				while current_node != adj:
					cicle.append(current_node)
					current_node = pi[current_node]
				cicle.append(adj)
				return cicle
	return None
digraph = get_input()
cicle = dfs(digraph)
if cicle is None:
	print('YES')
else:
	cicle.reverse()
	for i in range(len(cicle) - 1):
		c = dfs(digraph, cicle[i], cicle[i + 1])
		if c is None:
			print('YES')
			break
	else:
		print('NO')


def my_solve(n, m, graph, mask):
	if do_dfs_bool(n, graph, mask.copy()):
		c = get_cyclic(n, graph, mask)
		for (u, v) in c:
			graph[u].remove(v)
			if not do_dfs_bool(n, graph, mask.copy()):
				return 'YES'
			graph[u].append(v)
		return 'NO'
	return 'YES'

def get_cyclic(n, graph, mask):
	(c, v) = do_dfs(n, graph, mask)
	path = []
	i = 0
	begin = False
	if c:
		for u in c.keys():
			if c[u] == v:
				begin = True
				path.append((c[u], u))
			elif begin:
				path.append((c[u], u))
		tmp = list(c.keys())
		if len(tmp):
			path.append((tmp[-1], v))
	return path

def do_dfs_bool(n, graph, mask):
	colors = [0] * (n + 5)
	for u in graph.keys():
		if not u in mask.keys():
			if dfs_bool(u, graph, mask, colors):
				return True
	return False

def dfs_bool(u, graph, mask, colors):
	colors[u] = 1
	mask[u] = True
	for v in graph[u]:
		if colors[v] == 1:
			return True
		if colors[v] == 0:
			if dfs_bool(v, graph, mask, colors):
				return True
	colors[u] = 2
	return False

def do_dfs(n, graph, mask):
	colors = [0] * (n + 5)
	c = {}
	for u in graph.keys():
		if not u in mask.keys():
			c = {}
			(p, v) = dfs(u, graph, mask, c, colors)
			if p and v:
				return (p, v)

def dfs(u, graph, mask, c, colors):
	colors[u] = 1
	for v in graph[u]:
		if colors[v] == 1:
			return (c, v)
		if colors[v] == 0:
			c[v] = u
			(p, w) = dfs(v, graph, mask, c, colors)
			if w:
				return (p, w)
	colors[u] = 2
	if len(c) > 0:
		if u in c.keys():
			del c[u]
	return (c, None)

def test(n, m, edges):
	graph = {}
	mask = {}
	for (u, v) in edges:
		if u not in graph.keys():
			graph[u] = []
		graph[u].append(v)
		if v not in graph.keys():
			graph[v] = []
	return my_solve(n, m, graph, mask)

def __starting_point():
	(n, m) = [int(x) for x in input().split()]
	edges = []
	for i in range(0, m):
		(u, v) = [int(x) for x in input().split()]
		edges.append((u, v))
	print(test(n, m, edges))
__starting_point()


def detect_cycle(n, edges):
	visited = [False] * n
	stack = []
	color = [0] * n
	for v in range(n):
		if not visited[v]:
			if dfs_visit(v, edges, visited, stack, color):
				return stack
	return None

def dfs_visit(v, edges, visited, stack, color):
	visited[v] = True
	stack.append(v)
	color[v] = 1
	for u in edges[v]:
		if not visited[u]:
			if dfs_visit(u, edges, visited, stack, color):
				return True
		elif color[u] == 1:
			stack.append(u)
			return True
	color[v] = 2
	stack.pop(stack.index(v))
	return False
(n, m) = map(int, input().split())
edges = [[] for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	edges[u - 1].append(v - 1)
inCycle = detect_cycle(n, edges)
if inCycle:
	possible = False
	index = inCycle.index(inCycle[-1])
	inCycle = inCycle[index:]
	for v in range(len(inCycle) - 1):
		edges[inCycle[v]].remove(inCycle[v + 1])
		if detect_cycle(n, edges) is None:
			possible = True
			break
		else:
			edges[inCycle[v]].append(inCycle[v + 1])
else:
	possible = True
print('YES' if possible else 'NO')


(n, m) = [int(x) for x in input().split()]
a = [[] for i in range(n)]
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	a[u - 1].append(v - 1)
color = [0] * n
cycle = []
(blocked_u, blocked_v) = (-1, -1)

def dfs(u):
	nonlocal color
	nonlocal cycle
	if color[u]:
		return
	color[u] = 1
	for v in a[u]:
		if u == blocked_u and v == blocked_v:
			continue
		if color[v] == 0:
			dfs(v)
		if color[v] == 1 or cycle:
			if not cycle:
				cycle.append(v)
			cycle.append(u)
			return True
	color[u] = 2
	return False

def find_cycle():
	nonlocal color
	nonlocal cycle
	color = [0] * n
	cycle = []
	for u in range(n):
		if dfs(u):
			break
	result = cycle[::-1]
	return {(result[i], result[(i + 1) % len(result)]) for i in range(len(result))}
cur = find_cycle()
if not cur:
	print('YES')
	return
for (bu, bv) in cur:
	blocked_u = bu
	blocked_v = bv
	new = find_cycle()
	if not new:
		print('YES')
		return
print('NO')


(cycle_begin, cycle_end) = (-1, -1)
(g, mark, prev, edges) = ([], [], [], [])

def dfs(u):
	nonlocal cycle_begin, cycle_end
	mark[u] = 1
	for v in g[u]:
		if mark[v] == 0:
			prev[v] = u
			if dfs(v):
				return True
		elif mark[v] == 1:
			cycle_begin = v
			cycle_end = u
			return True
	mark[u] = 2
	return False

def dfs2(u):
	mark[u] = 1
	for v in g[u]:
		if v != -1:
			if mark[v] == 0:
				if dfs2(v):
					return True
			elif mark[v] == 1:
				return True
	mark[u] = 2
	return False
(n, m) = list(map(int, input().split()))
g = [[] for i in range(n)]
mark = [0 for i in range(n)]
prev = [-1 for i in range(n)]
for i in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	g[u].append(v)
for i in range(n):
	if mark[i] == 0 and dfs(i):
		break
if cycle_begin == -1:
	print('YES')
else:
	cycle = []
	i = cycle_end
	while i != cycle_begin:
		cycle.append(i)
		i = prev[i]
	cycle.append(cycle_begin)
	cycle.reverse()
	edges = []
	for i in range(len(cycle) - 1):
		edges.append(tuple((cycle[i], cycle[i + 1])))
	edges.append(tuple((cycle[len(cycle) - 1], cycle[0])))
	can = False
	while len(edges) > 0:
		f = edges[0][0]
		s = edges[0][1]
		g[f][g[f].index(s)] = -1
		mark = [0 for i in range(n)]
		have = False
		for i in range(n):
			if mark[i] == 0 and dfs2(i):
				have = True
				break
		g[f][g[f].index(-1)] = s
		if not have:
			can = True
			break
		edges.pop(0)
	if can:
		print('YES')
	else:
		print('NO')


def dfs(g, u, visited, call_stack):
	visited[u] = True
	call_stack.add(u)
	for v in g[u]:
		if v in call_stack:
			return [u, v]
		if not visited[v]:
			d = dfs(g, v, visited, call_stack)
			call_stack.discard(v)
			if d is not None:
				return [u] + d
	return None

def find_cycle(g, n):
	visited = [False] * n
	d = None
	for i in range(n):
		if not visited[i]:
			call_stack = set()
			d = dfs(g, i, visited, call_stack)
			if d is not None:
				break
	return d
(n, m) = map(int, input().split())
g = []
for _ in range(n):
	g.append([])
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
out = False
c = find_cycle(g, n)
if c:
	first_index = c.index(c[-1])
	c = c[first_index:]
	for i in range(len(c) - 1):
		if i != 0:
			g[c[i - 1]].append(c[i])
		g[c[i]].remove(c[i + 1])
		out = out or find_cycle(g, n) is None
else:
	out = True
print('YES' if out else 'NO')


import sys

def prepare():
	stack = [i for i in range(n) if deg[i] == 0]
	cnt = 0
	while stack:
		v = stack.pop()
		cnt += 1
		for dest in adj[v]:
			deg[dest] -= 1
			if deg[dest] == 0:
				stack.append(dest)
		adj[v].clear()
	return cnt == n

def solve(st):
	stack = [st]
	visited = [0] * n
	cnt = 0
	while stack:
		v = stack.pop()
		cnt += 1
		for dest in adj[v]:
			if dest == st:
				continue
			visited[dest] += 1
			if deg[dest] == visited[dest]:
				stack.append(dest)
	return cnt == m
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
adj = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
deg = [0] * n
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].append(v - 1)
	rev[v - 1].append(u - 1)
	deg[v - 1] += 1
ok = prepare()
if ok:
	print('YES')
	exit()
m = len([1 for i in range(n) if deg[i] > 0])
for i in range(n):
	if deg[i] == 1 and solve(i):
		print('YES')
		exit()
print('NO')