Time Limit: 2 Seconds
Memory Limit: 65536 KB
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 of (at least two) points. Each two adjacent points are connected by an edge. Suika's chain looks slightly different. There are three sub-chains extended from the main chain from three different points. At the end of each sub-chain, there is a simple cycle with length 3, 4 or 5, represents the tetrahedron, the block and the ball respectively. There must be no other 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.
There 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 Xi and Yi (1 <= Xi, Yi <= N) represents the points the i-th edge connected.
20 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