Description
There are N distinct points on a paper, labeled from 1 to N. You are asked to draw a path connecting all the points, and each point is allowed to be visited more than once. For example, the following 5 points can be connected into the shape of a house in the order of 1,4,2,3,4,5,3,1,2.
Now, you need a program to check whether the graph can be drawn by only one stroke. Since you have already checked that all the points are connected, there must be a path for any one point to reach another.
Input
There are several test cases, but no more than 10 test cases. In each test case, there’re two numbers N and M in the first line, indicating that there’re N points and M lines on the paper. Each line can be used only once.
In the next M lines, each line contains two numbers i and j, which means there’s a line connecting point i and point j.
- 1 <= N <= 10^4
- N-1 <= M <= 10^5
- 1 <= i, j <= N
- The given graph contains only one connected component which connects all the points. There’s no a point that cannot reach all the other points.
Output
If the graph can be drawn by only one stroke, print Yes; otherwise, print No.
Hint:
If a graph G has an Eulerian path, then it must have exactly two odd vertices.
1. Suppose that a graph has an Eulerian path P, which can be drawn by only one stroke. For every vertex v other than the starting and ending vertices, the path P enters v the same number of times that it leaves v (say s times). Therefore, there are 2s edges having v as an endpoint. Therefore, all vertices other than the two endpoints of P must be even vertices.
2. Suppose the Eulerian path P starts at vertex x and ends at vertex y. The P leaves x one more time than it enters, and leaves y one fewer time than it enters. Therefore, the two endpoints of P must be odd vertices.
*Note that if the path starts and ends at the same vertex, there's no odd vertex.
Reference: https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf