영국 요리 코스

시간 제한5초메모리 제한1024 MB

요약

사이클이 같은 요리를 다시 포함할 때 그 사이에 서로 다른 요리가 최대 네 개까지만 끼는 방향 그래프가 주어질 때, 같은 정점을 두 번 쓰지 않는 가장 긴 경로의 길이를 구한다.}|||{

난이도: 어려움10점 중 9점
유형: 그래프, 동적 계획법, BFS, 구현
정답자: 아직 제출이 없습니다

문제

영국에 머무는 저녁이 하루뿐이라, 한 자리에서 영국 요리를 최대한 많이 먹기로 했다. 요리를 아무 순서로나 이어 먹을 수는 없다. 예를 들어 콘월식 헤바 케이크 바로 다음에 블랙 푸딩을 먹는 것은 안 되지만, 그 사이에 베이크드 빈스를 하나 끼워 넣으면 괜찮다.

요리 목록을 만들면서 각 요리마다 그 요리 바로 다음에 먹어도 되는 요리를 모두 적어 두었다. 코스는 요리를 나열한 것이고, 첫 요리를 뺀 모든 요리는 바로 앞 요리 다음에 먹어도 되는 요리여야 한다.

목록에는 성질이 하나 있다. 같은 요리가 두 번 들어가는 코스를 만들 수 있을 때, 그 두 번 사이에 들어가는 서로 다른 요리는 그 요리 자신을 빼고 최대 네 가지다. 그래서 A, B, C, D, E, F, A 같은 코스는 만들 수 없지만, A, B, C, B, C, B, C, B, C, B, A나 A, B, C, D, E, A, B, C, D, E, A 같은 코스는 만들 수 있다.

같은 요리를 두 번 먹고 싶지는 않다. 어떤 요리도 두 번 나오지 않는 코스에 요리를 최대 몇 가지 넣을 수 있는지 구하라.

입력

첫째 줄에 요리의 수 $n$ 과 이어 먹어도 되는 쌍의 수 $m$ 이 주어진다 ( $1 \le n \le 10^5$ , $1 \le m \le 10^6$ ).

다음 $m$ 개 줄에 정수 $a$ 와 $b$ 가 주어진다 ( $1 \le a \le n$ , $1 \le b \le n$ ). 요리 $a$ 바로 다음에 요리 $b$ 를 먹어도 된다는 뜻이다.

요리에는 1번부터 $n$ 번까지 번호가 붙어 있고 번호 순서에 특별한 뜻은 없다. 같은 쌍이 여러 번 주어질 수 있고, $a$ 와 $b$ 가 같을 수도 있다. 주어지는 쌍은 위에서 설명한 성질을 만족한다.

출력

같은 요리가 두 번 나오지 않는 코스에 들어갈 수 있는 요리 수의 최댓값을 한 줄에 출력한다.

예제2

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