A directed graph is a set V of vertices and a set of E ∈ {V x V} 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
(u1, v1), (u2, v2),…, (uk, vk)
such that ui+1 = vi for i = 1, …, k-1, and u1=vk. The directed cycle is simple if ui ≠ uj whenever i ≠ 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. 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.
For each test case output a single line with a single string. Output "YES" if the graph is a cactus, and output "NO" if it is not.
2 4 5 0 1 1 2 2 0 2 3 3 2 4 5 0 1 1 2 2 3 3 0 1 3
YES NO