ZOJ Problem Set - 3330
As you know, in a Tree there is exactly one path between two nodes. A Forest consists of one or more Trees. Country F has N cities, some cities are connected by roads, and these cites form a Forest with at least two trees.
The king of country F is a man with special ideas. He wants to make any two trees in the forest isomorphic. We say that two trees are isomorphic if they have same structure. That is to say, if we ignore the indices of all the nodes, the two trees are the same.
For example, in the picture shown above, the middle tree and the right tree are isomorphic, but the middle tree and the left tree are not isomorphic.
Because it is expensive to build roads, the King decides only to destroy edges. But if too many roads are destroyed, people in country F will be angry, so he can destroy at most ONE road.
Now, the King asks you whether it is possible to make any two trees isomorphic, if he destroys at most one road.
There are multiple cases (no more than 60). For each case, the first line is two integers N and M (2 <= N <= 10000, 0 <= M <= N - 2), giving the number of cities and number of roads. M lines follow, each with two integers x and y (0 <= x, y < N, x != y), means there is a road between city x and city y. You may assume that there is at most one road between any two cities and the cities forms a forest with at least two trees.
The last case is followed by two zeros.
For each case, if it is possible for the King to make any two trees isomorphic when destroying at most one road, output "Yes", otherwise output "No".
9 7 0 1 0 2 1 3 3 4 3 5 6 7 6 8 9 7 0 1 1 2 1 3 3 4 3 5 6 7 6 8 5 2 0 1 1 2 0 0
Yes Yes No
Author: HANG, Hang
Source: The 7th Zhejiang Provincial Collegiate Programming Contest