Hide

Problem B
Cactus

/problems/cactus/file/statement/en/img-0001.jpg
A directed graph is a set $V$ of 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.

\includegraphics[width=0.5\textwidth ]{samples}
Figure 1: Sample Inputs 1 and 2

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

Please log in to submit a solution to this problem

Log in