ABCDE

An algorithm camp has $N$ participants. They are numbered from $0$ to $N-1$, and some pairs of them are friends.

Decide whether there are people A, B, C, D, E with all of the following friendships.

• A and B are friends.
• B and C are friends.
• C and D are friends.
• D and E are friends.

A, B, C, D, E must be five different people. Write a program that decides whether such five people exist.

The first line contains the number of people $N$ ($5 \le N \le 2000$) and the number of friendships $M$ ($1 \le M \le 2000$).

Each of the next $M$ lines contains two integers $a$ and $b$, meaning that person $a$ and person $b$ are friends. ($0 \le a, b \le N-1$, $a \ne b$) The same friendship is never given more than once. Friendship has no direction, so if $a$ is a friend of $b$, then $b$ is a friend of $a$.

Print 1 if A, B, C, D, E satisfying the conditions exist, and 0 otherwise.