
ZOJ Problem Set  3906
As the only Oni (a kind of fabulous creature with incredible strength and power) living on the surface of Gensokyo, Ibuki Suika always wears a powerful and mysterious chain. The chain is a symbolization of Oni. Not surprisingly, Suika's chain looks very different from her friends' chains. There are three small magical artifacts hanging on the chain:
One day, you have discovered an ancient tome recording the history of Gensokyo. On the 725th page of the tome, you were attracted by a stange graph consists of N points and M edges. Each edge connects two points. After a short time of reasearch, you have realized that the graph may represents the chain of Suika. An ordinary chain is a graph consists of a sequential (at least two) points. Each two adjacent points are connected by an edge. Suika's chain looks slightly different. There are three subchains extended from the main chain from three different points. At the end of each subchain, there is a simple cycle with length 3, 4 or 5, represents the tetrahedron, the block and the ball respectively. There is no useless points or edges in the graph of Suika's chain. Checking the graph manually seems to be an inefficient method. So you decide to write a small program to judge whether the graph represents the chain of Suika or not. InputThere are multiple test cases. For each test case: The first line contains two integers N (1 <= N <= 50) and M indicating the number of points and edges in the graph. Then followed by M lines, each line contains two integers X_{i} and Y_{i} (1 <= X_{i}, Y_{i} <= N) represents the points the ith edge connected. OutputFor each test case, output "Yes" if the graph represents the chain of Suika, or "No" if not. Sample Input20 22 1 2 2 3 3 4 4 5 5 6 2 7 7 8 8 9 9 10 10 11 11 12 12 8 3 13 13 14 14 15 15 16 16 13 5 17 17 18 18 19 19 20 20 18 5 6 1 2 2 3 3 4 4 5 5 1 1 3 Sample OutputYes No HintThis is what the first sample test case looks like:
Author: JIANG, Kai Source: ZOJ Monthly, October 2015 