ABCDE

Interview

Time limit2sMemory limit512 MB

Summary

Given an undirected friendship graph, decide whether it contains a simple path of five distinct vertices, that is, a path with four edges.

Level: Medium5 of 10
Topics: Graph, DFS, Backtracking, Brute force
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Examples4

Example 1
Input
```
5 4
0 1
1 2
2 3
3 4
```
Expected output
```
1
```
Example 2
Input
```
5 5
0 1
1 2
2 3
3 0
1 4
```
Expected output
```
1
```
Example 3
Input
```
6 5
0 1
0 2
0 3
0 4
0 5
```
Expected output
```
0
```
Example 4
Input
```
8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7
```
Expected output
```
1
```