# Problem C

Cactus

*vertices*and a set $E\subseteq V\times V$ of

*edges*. An edge $(u,v)$ is said to be directed from $u$ to $v$ (the edge $(v,u)$ has the opposite direction). A directed cycle in a directed graph is a sequence of edges $\left<(u_1, v_1),\ldots ,(u_ k, v_ k)\right>$ such that $u_{i+1} = v_ i$ for $i = 1,\ldots ,k-1$, and $u_1=v_ k$. The directed cycle is

*simple*if $u_ i \neq u_ j$ whenever $i\neq j$ (i.e., if it does not pass through a vertex twice).

In a *strongly connected* directed graph, there is
for every pair $u,v$ of
vertices some directed cycle (not necessarily simple) that
visits both $u$ and
$v$.

A directed graph is a *cactus* if and only if it is
strongly connected and each edge is part of exactly one
directed simple cycle. In Figure 1, the first graph is a
cactus, but the second one is not since for instance the edge
$(0,1)$ is in two simple
cycles.

The reason for the name is that a “cactus” consists of several simple cycles connected to each other in a tree-like fashion, making it look somewhat like a cactus.

Write a program that given a directed graph determines if it is a cactus or not. The graph can have several thousand vertices.

## Input

The first line of input contains two integers $n$ and $m$, where $1 \le n \le 200\, 000$ is the number of vertices and $0 \le m \le 200\, 000$ is the number of edges in the graph. The vertices are numbered $0$ through $n-1$. The following $m$ lines describe the edges as pairs of numbers $u$ $v$ denoting an edge directed from $u$ to $v$. There will never be more than one edge from $u$ to $v$ for any pair of vertices $u$ and $v$. There are no loops, i.e., no edges from a vertex to itself.

## Output

If the graph is a cactus, output “`YES`”, otherwise output “`NO`”.

Sample Input 1 | Sample Output 1 |
---|---|

4 5 0 1 1 2 2 0 2 3 3 2 |
YES |

Sample Input 2 | Sample Output 2 |
---|---|

4 5 0 1 1 2 2 3 3 0 1 3 |
NO |