Problem P
Furry Nuisance

In order to protect himself from evil bunnies, Freddy decided to install an automatic system to detect them in pictures from surveillance cameras. Sophisticated software detects important points in the picture and lines between them. Unfortunately, the terrain in the pictures is quite varied and lot of the points and lines are actually not bunnies.

You have made the following observation: Each bunny has four paws and a body joining them. Based on this observation, write a program to decide whether a given picture can possibly contain a bunny.

A picture of a bunny consists of points that are connected by lines and the whole picture is connected: a picture is connected if (and only if) each two points in the picture are joined with each other by one or more successive lines. A paw is a point which is directly joined with exactly one other point.

\includegraphics[width=0.95\textwidth ]{bunny1}

\includegraphics[width=0.95\textwidth ]{bunny2}

Figure 1: Two examples of bunnies. Each one has 4 paws marked as green nodes.


The input contains several test cases. The first line of each test case contains two integers $n$ and $m$ ($0\le n\le 10\, 000$, $0\le m\le 20\, 000$), giving the number of points and lines in the image, respectively. Each of the $m$ following lines contains two distinct integers $x$ and $y$ ($1\le x,y\le n$), indicating that the points $x$ and $y$ are directly joined by a line.

You may assume that each pair of points is joined by at most one direct line and that no point is directly joined with itself.

The total number of test cases is 1 million and the size of the input is at most 10 megabytes.


For each input instance, output “YES” if the picture contains a bunny, and “NO” otherwise. The picture contains a bunny if it is possible to remove some of the points and lines so that the resulting image is connected and has exactly $4$ paws.

Sample Input 1 Sample Output 1
2 1
1 2
5 4
1 2
1 3
1 4
1 5

Please log in to submit a solution to this problem

Log in