31568번 - 산림의 수호자

문제

근성은 나무에 관심이 많다.

드루이드 근성은 나무를 관리하는 산림의 수호자이다. 근성이 관리하는 나무는 트리 형태를 이루고 있으며, 얼마나 관리가 잘 됐는지 무려 $N$개나 되는 정점을 가지고 있다. 근성은 모든 정점을 소중하게 여겨서 $N$개의 정점들에 각각 1ドル$에서부터 $N$까지의 고유한 정점 번호를 일일이 매겨놓았다.

어느 날, 근성의 멋진 나무를 항상 시기해 오던 사악한 악당 영도가 근성의 나무에 불을 지르고 말았다! 근성이 나무를 최대한 온전히 보존하기 위해서는, 나무가 완전히 타서 없어지기 전에 나무의 각 정점에 저장된 데이터들을 최대한 많이 복제해야 한다.

초기에 영도는 $a$번 정점을 불태웠고, 근성은 불에 타지 않은 $b$번 정점 위에 서 있다. 근성은 불에 타지 않은 정점 위에서 다음 행동 중 하나를 선택하여 수행할 수 있다.

• 복제하기: 근성이 현재 정점에서 데이터를 복제한다. 이 행동은 시간을 소모하지 않는다. 단, 데이터를 이미 복제한 정점에서는 다시 데이터를 복제할 수 없다.
• 이동하기: 근성이 현재 정점에서 간선을 따라 이웃한 불에 타지 않은 정점 중 한 곳으로 이동한다.
• 기다리기: 근성이 현재 정점에서 이동하지 않고 대기한다.

만약 근성이 이동하기 또는 기다리기를 선택했다면, 수행하는 시간 동안 불타는 정점과 이웃한 관계에 있는 아직 불타지 않는 정점들로 불이 옮겨 붙는다.

만약 근성이 다음 행동으로 불타는 정점 위에 있게 된다면, 그 즉시 근성은 더 이상의 나무 보존 작업을 포기하고 나무에서 탈출할 것이다. 근성이 정점에 도착함과 동시에 해당 정점으로 불이 옮겨붙는다면 근성은 해당 정점에서 데이터를 복제할 수 없다.

당신이 해야 할 일은 근성이 탈출하기 전까지 데이터를 복제할 수 있는 나무의 정점 개수의 최댓값을 구하여 근성에게 알려주는 것이다. 산림의 수호자 근성이 최대한 많은 데이터를 보존할 수 있도록 도와주자!

입력

첫 번째 줄에 나무의 정점의 개수 $N$이 주어진다.

두 번째 줄부터 $N-1$개의 줄에 걸쳐 나무의 간선 정보 $u, v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점 사이에 간선이 존재한다는 뜻이다.

$N+1$번째 줄에 최초로 불타는 $a$번 정점과 근성이 위치한 $b$번 정점의 번호가 공백으로 구분되어 주어진다.

출력

가능한 모든 경우들 중 근성이 탈출하기 전까지 데이터를 복제할 수 있는 나무의 정점 개수의 최댓값을 출력한다.

제한

• 2ドル \le N \le 100,000円$
• 1ドル \le a, b, u, v \le N$
• $a \neq b$
• 입력으로 주어지는 모든 수는 정수이다.
• 입력으로 주어지는 모든 나무는 올바른 트리이다.

노트

다음 그림은 예제 입력 1에서 주어진 나무의 모습이다. 이 문제에서 나무는 트리 형태를 이루고 있으며, 트리는 사이클이 없는 단순 연결 그래프를 의미한다. 주어진 예제 그림은 사이클이 없는 단순 연결 그래프의 모습을 만족하고 있다.

이 예제의 경우 근성이 복제할 수 있는 정점 데이터의 최대 개수는 3개이다. 가능한 최적의 행동 중 하나는, 기다리기를 선택하지 않고 4ドル$($b$)→2ドル$→1ドル$ 순서대로 이동하기를 선택하면서 매 정점마다 복제하기를 선택하는 것이다.