난쟁이와 외로운 산

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

요약

트리에서 두 그룹이 각자 출발한 동굴에서 서로 겹치지 않는 경로로 최대한 오래 이동할 때, 그 분 수를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

난쟁이들은 조상의 황금을 외로운 산의 지하에서 계속 찾고 있다. 지하에는 $n$ 개의 동굴이 있고, 일부 동굴은 양방향 통로로 연결되어 있다. 모든 동굴에서 다른 어떤 동굴로도 통로를 따라 갈 수 있으며, 그 방법은 단 하나뿐이다.

난쟁이들은 두 무리로 나뉘어 각각 동굴 $u_0$ 와 $v_0$ 에서 탐사를 시작한다. 각 무리는 항상 함께 움직인다. 무리는 동굴을 조사하는 데 정확히 1분이 걸리고, 그 뒤 통로를 지나 인접한 동굴 중 하나로 빠르게 이동한다. 무리는 자신들이나 다른 무리가 이미 방문한 동굴에는 들어가지 않는다. 두 무리는 같은 동굴에 들어가지 않는다. 두 무리 중 하나라도 이 규칙에 따라 이동할 수 없으면, 두 무리는 즉시 탐사를 멈춘다.

난쟁이들은 탐사를 최대한 오래 하고 싶어 한다. 동굴 지도와 두 무리의 시작 위치가 주어질 때, 탐사가 최대 몇 분 동안 계속될 수 있는지 구하라.

입력

첫 줄에 동굴의 수 $n$ ( $2 \le n \le 200\,000$ )이 주어진다. 다음 $n - 1$ 개 줄에는 통로로 연결된 두 동굴의 번호 $v$ 와 $u$ ( $1 \le v, u \le n$ )가 주어진다. 마지막 줄에는 두 무리의 시작 동굴 번호 $v_0$ 와 $u_0$ ( $1 \le v_0, u_0 \le n$ , $v_0 \ne u_0$ )가 주어진다.

출력

탐사가 계속될 수 있는 최대 시간(분)을 출력한다.

예제2

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