DFS + Cycles + Cactus
In the city of N in the near future will take place the world championship car racing among the cars of Formula-0. As the organisers haven't the time to build a special race track for these competitions, it was decided to organise a track in the streets of the city.
In the city of N there are n intersections, some pairs of which are connected by roads, the movement which is possible in both directions. In this case, any two of the intersection are connected by no more than one way, and it is possible to reach by road from any intersection before anyone else.
The route, where every competition will be held must be circular (i.e. should start and finish at the same intersection), while in the process of movement along it the crossing should occur no more than once.
At the preliminary stage of preparation of the organising committee was set up a list of all city roads. Now it's time to use it. The first question that must be addressed - is the question of existence in the desired circular route (of course, if the answer is negative, the organisers will have to urgently build some more roads). The only problem is that the organisers have a suspicion that, since the list was compiled not too closely, it has some of the roads listed more than once.
Write a program that, given the list of roads in the city, determine is it possible to organize the desired circular track.
The first line contains two integers: n (1 ≤ n ≤ 1000) - the number of intersections in the city of N and m (0 ≤ m ≤
105) - the number of roads in the compiled list.
Following m lines describe the roads. Each road is given by two numbers: u and v (1 ≤ u, v ≤ n, u ≠ v) - the numbers of intersections that it connects. Since the roads are bidirectional, the pair (u, v) and a pair (v, u) describes the same road.
Print YES, if the city might organise a circular track for competition, and the word NO otherwise.
3 4 1 2 2 3 3 1 3 2
2 3 1 2 2 1 2 1