After years of toil designing and evaluating varieties of complex networks, Michelle, an elite engineer, has recently made the decision to develop an assistant software to help herself out.
Consider a network built up with undirected water supply pipes each connecting a pair of junctions that supply or consume water. A shortcut of length L is defined as a sequence of L distinct junctions such that two junctions are adjacent in the network if and only if they are adjacent in the sequence. A network is regarded speedy if there is no shortcut with a length greater than three.
Now, please try to work out an efficient solution for Michelle to determine whether a network is speedy or not.
The input contains exactly one test case given as specified below:
| Line 1 | Two integers N (1 < N < 1,200) and M, which are the numbers of junctions and pipes, respectively. |
| Line 2 – M + 1 | Two integer A and B (1 ≤ A, B ≤ N) on each line, describing a pipe connecting junctions A and B. |
You can assume that there exists a path between any two junctions.
Output “Yes” if the network is speedy, otherwise print “No”.
4 4 1 2 2 3 3 4 4 1
Yes