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: interview

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')

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 # 0 - white, 1 - grey, 2 - black
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 # 0 - white, 1 - grey, 2 - black
    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')


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


def __starting_point():
    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')
__starting_point()

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")


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


def dfs(u):
    nonlocal 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 = list(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 = 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:
    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")
            return

    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")




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()

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


def __starting_point():
    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")

__starting_point()