ABCDE

면접 대비

시간 제한2초메모리 제한512 MB

요약

무방향 친구 관계 그래프가 주어질 때, 서로 다른 다섯 명이 네 번의 친구 관계로 이어지는 단순 경로가 존재하는지 판별한다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 백트래킹, 완전 탐색
정답자: 아직 제출이 없습니다

문제

알고리즘 캠프에 $N$ 명이 참가하고 있다. 참가자에게는 $0$ 번부터 $N-1$ 번까지 번호가 붙어 있고, 그중 일부는 서로 친구다.

다음 친구 관계를 모두 만족하는 사람 A, B, C, D, E가 있는지 판정하려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

A, B, C, D, E는 서로 다른 다섯 사람이어야 한다. 이런 다섯 사람이 존재하는지 판정하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 $N$ ( $5 \le N \le 2000$ )과 친구 관계의 수 $M$ ( $1 \le M \le 2000$ )이 주어진다.

둘째 줄부터 $M$ 개의 줄에 정수 $a$ 와 $b$ 가 주어지며, $a$ 번 사람과 $b$ 번 사람이 친구라는 뜻이다. ( $0 \le a, b \le N-1$ , $a \ne b$ ) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다. 친구 관계에는 방향이 없어서 $a$ 가 $b$ 의 친구면 $b$ 도 $a$ 의 친구다.

출력

조건을 만족하는 A, B, C, D, E가 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제4

예제 1
입력
```
5 4
0 1
1 2
2 3
3 4
```
예상 출력
```
1
```
예제 2
입력
```
5 5
0 1
1 2
2 3
3 0
1 4
```
예상 출력
```
1
```
예제 3
입력
```
6 5
0 1
0 2
0 3
0 4
0 5
```
예상 출력
```
0
```
예제 4
입력
```
8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7
```
예상 출력
```
1
```