배달 로봇

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

요약

연결된 무방향 그래프에서 시작점 s와 끝점 f를 골라, 두 점을 잇는 단순 경로 위에 놓일 수 있는 정점 수의 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 트리
정답자: 아직 제출이 없습니다

문제

주쿠는 핫도그를 좋아한다. 아주 많이.

주쿠가 사는 마을에는 교차로가 $V$ 개 있고, 교차로를 잇는 양방향 도로가 $E$ 개 있다. 교차로에는 $1 \ldots V$ 의 번호가 매겨져 있다. 두 교차로를 잇는 도로는 최대 하나이고, 교차로에서 자기 자신으로 이어지는 도로는 없다. 어느 교차로에서든 도로를 따라 다른 모든 교차로에 갈 수 있다. 각 교차로에는 핫도그 가판대가 하나씩 있다.

주쿠는 자신에게 핫도그를 가져다줄 배달 로봇을 만들고 있다. 로봇의 출발 위치인 교차로 $s$ 와 주쿠의 위치인 교차로 $f$ 를 고르고, 가능한 한 많은 서로 다른 가판대에서 핫도그를 받을 수 있도록 로봇을 프로그래밍한다.

로봇 프로그래밍에는 제약이 있다. 각 로봇은 배열 $n$ 과 변수 $b$ 를 저장할 수 있다. 로봇은 교차로 $s$ 에서 출발해 다음 과정을 반복한다.

로봇이 교차로 $b$ 에 있으면, 그곳 가판대에서 핫도그를 산다.
로봇이 교차로 $f$ 에 있으면, 핫도그를 주쿠에게 주고 멈춘다.
로봇은 현재 위치 $i$ 에서 교차로 $n[i]$ 로 이동한다.

모든 $i \in 1 \ldots V$ 에 대해 교차로 $i$ 와 $n[i]$ 사이에는 도로가 있어야 한다. 그렇지 않으면 로봇이 고장 난다.

주쿠가 $s$ 와 $f$ 를 최적으로 고르고, $n$ 과 $b$ 도 로봇에 최적으로 입력할 때, 주쿠가 핫도그를 받을 수 있는 서로 다른 가판대의 최대 개수를 구하라. $s$ 와 $f$ 는 모든 로봇에 공통이지만, $n$ 과 $b$ 는 로봇마다 다를 수 있다. 로봇은 원하는 만큼 많이 쓸 수 있다고 가정해도 된다.

입력

첫 줄에 교차로 수 $V$ 와 도로 수 $E$ 가 공백으로 구분되어 주어진다 ( $1 \le V \le 10^5$ , $1 \le E \le 3 \cdot 10^5$ ). 이후 $E$ 개의 줄에는 각각 도로로 연결된 두 교차로 $u$ 와 $v$ 가 주어진다.

출력

주쿠가 핫도그를 받을 수 있는 서로 다른 가판대의 최대 개수를 한 개의 정수로 출력한다.

예제1

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