Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Şehmettin is METU's cursed maze's guard. He encountered World's cutest german shepherd Zeyna while he was patrolling around the maze. Şehmettin, being a bad person as he is, decided to steal Zeyna's food and run away to the cursed maze to escape from Zeyna afterward. He knew that roads between intersections would collapse after someone walks on them because of the curse of the maze.

To escape, Şehmettin has to destroy all the roads in the maze. The roads will collapse after someone walks on them. Zeyna can catch him if Şehmettin doesn't destroy all the roads. It doesn't matter if Şehmettin is at the same intersection or not at the end of destruction. Your duty is to check whether Şehmettin can destroy all roads without using the same road twice.

Şehmettin can use intersections more than once but can not use a road twice. In the end, he doesn't need to cross all the intersections, only the roads have to be destroyed in order to escape.

To save himself, he should destroy all the roads.


The first line will contain 1 integer, \(\mathbf{N}\) how many roads there are between intersections.

Next \(\mathbf{N}\) lines will contain 2 integers \(\mathbf{A}\) and \(\mathbf{B}\), which means there is a road between \(\mathbf{A}\) and \(\mathbf{B}\) intersections.

  • \(1 \leq \mathbf{N} \leq 10^{5}\)
  • \(1 \leq \mathbf{A}, \mathbf{B} \leq 10^{5}\)


If Şehmettin can save himself print "YES" otherwise print "NO".



3 2
2 1
4 3
2 4




2 3
3 1
4 2
1 4
6 5




Input 1

Şehmettin can start from the \(1^{\mathbf{st}}\) intersection and follow the path 1 -> 2 -> 3 -> 4 -> 2 to destroy all the roads.

Input 2

There are no possible intersections that Şehmettin can start and destroy all the roads.