페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4028

제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

가지치기 3초 1024MB

문제

정점 N개로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다.

트리에서 두 정점 사이의 거리는 두 정점을 연결하는 경로에서 지나야 하는 간선의 수이다.

가지치기라는 연산을 통해 배열 P를 만들 수 있다.

  1. 정점 V를 선택한다.

  2. V에서 가장 거리가 먼 정점 중 가장 작은 번호를 가진 정점을 트리에서 삭제한다.

  3. 트리의 정점이 모두 없어질 때까지 2. 를 반복한다.

P[i]가 i+1번째로 삭제된 정점의 번호일때, P를 사전순으로 가장 작게 하는 V를 구하시오.

다른 두 배열 P, Q에 대해, P가 Q보다 사전순으로 작다는 것은 P[i]≠Q[i]인 가장 작은 i에 대해 P[i]<Q[i]인 경우를 의미한다.


입력

첫 번째 줄에 N이 주어진다. (2≤N≤300\ 000) 두 번째 줄부터 N−1개의 줄에 걸쳐 트리를 이루는 간선으로 연결된 두 정점 u, v가 공백으로 구분되어 주어진다. (1≤u,v ≤N;\ u≠v)


출력

첫 번째 줄에 P를 사전순으로 가장 작게 하는 V를 출력한다.


예제 

3
3 1
1 2
3
로그인해야 코드를 작성할 수 있어요.