Lawyers

Interview

Time limit1sMemory limit512 MB

Summary

Given N lawyers and M directed trust edges, decide whether every lawyer has at least one incoming edge and no two lawyers defend each other.

Level: Medium4 of 10
Topics: Graph, Implementation
Solved: No attempts yet

Problem

$N$ lawyers are charged with fraud. The $N$ lawyers want to defend each other so that all of them are acquitted.

A lawyer can be defended only by a lawyer they trust. Trust is given as $M$ pairs $(A, B)$ , meaning lawyer $B$ trusts lawyer $A$ . Only in that case can lawyer $A$ defend lawyer $B$ .

The lawyers are highly skilled, so anyone defended by at least one lawyer is acquitted without exception. However, if $A$ defends $B$ and $B$ defends $A$ , both are found guilty, because such a pair is highly suspicious.

For each pair $(A, B)$ , decide whether lawyer $A$ defends lawyer $B$ . Determine whether it is possible for every lawyer to be acquitted.

Input

The first line contains $N$ and $M$ . ( $1 \le N, M \le 200,000$ )

From the second line onward, the $i$ -th of the next $M$ lines contains two distinct integers $A_i$ and $B_i$ . This means lawyer $A_i$ can defend lawyer $B_i$ .

No ordered pair $(A, B)$ appears more than once in the input.

Output

If every lawyer can be defended by at least one lawyer and there is no pair of lawyers who defend each other, print YES on the first line.

Otherwise, print NO on the first line.

Examples3

Example 1
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
YES
```
Example 2
Input
```
4 6
1 2
1 3
1 4
2 3
2 4
3 4
```
Expected output
```
NO
```
Example 3
Input
```
4 4
1 2
2 1
3 4
4 3
```
Expected output
```
NO
```