# Topological Sorting

Given a directed graph with

`v`

vertices and `e`

edges, you would like to sort the vertices in a particular order. If there is an edge that goes from `v1`

to `v2`

, then the source vertex `v1`

should appear earlier in the array of vertices than `v2`

. So, after sorting the vertices, each edge should take one from a vertex with a smaller index to a vertex with a larger one.🤔

Notice that there can be different valid topological sorting orders.
On the other hand, if the graph contains cycles, there are no valid topological sorting orders.

The algorithm can be implemented with a DFS that starts from every vertex which hasn’t been visited so far. On each DFS iteration, we can first recursively add all the child nodes of the current vertex, and only after all the child vertices are processed, add the current one to the answer list. This will ensure that the source vertex appears

**later**than all the ones reachable from it. By the end of the algorithm, we will reverse the order in the answer list:```
used = [False] * n # used vertices
order = [] # topological order
def dfs(v): # dfs
used[v] = True # mark vertex as used
for to in g[v]: # for each vertex to adjacent to v
if not used[to]: # if to is not used
dfs(to) # dfs from to
order.append(v) # add v to topological order
for i in range(n): # for each vertex
if not used[i]: # if vertex is not used
dfs(i) # dfs from vertex
print(*order[::-1]) # print topological order
```

Challenge: Organize the Course Schedule

You are given

`n`

courses that you’d like to take. There are `p`

prerequisites in total. Each prerequisite represents a pair of courses

meaning that you must take the course

before you take course

(if the pair is 1, 2 - it means that you need to take course 2 before taking course 1).You need to check if it’s possible to finish all the courses.

Input

The first line of the input contains two integers

`n`

and `p`

(1 ≤ n, p ≤ 10 000).The next

`p`

lines contain pairs of integers

(1 ≤ ≤ n). Output

The program should print

`Yes`

if it’s possible to take all the courses and `No`

otherwise. Examples

Input | Output |

2 1
2 1 | Yes |

2 2
2 1
1 2 | No |

#### Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB