역

바이트오시아의 철도망은 역들을 잇는 양방향 선로 구간들로 이루어져 있다. 어떤 두 역도 두 개 이상의 구간으로 직접 연결되어 있지 않으며, 모든 역은 다른 모든 역으로부터 정확히 하나의 단순 경로로 도달할 수 있다. 즉, 이 철도망은 트리를 이룬다.

이번 개혁 단계에서는 하나의 중심 역을 기준으로 열차 노선을 구성한다. 정확히 한 역을 골라 Bitwise 라는 이름의 거대한 허브로 삼는다. 나머지 각 역마다, Bitwise 와 그 역 사이의 유일한 경로를 따라 달리며 중간의 모든 역에 정차하는 노선을 하나씩 만든다. 따라서 노선은 모두 $n-1$ 개이다.

승차권은 편도이며 한 번만 쓸 수 있다. 승차권 한 장으로는 구간 수가 아무리 많더라도 노선 하나 전체(또는 그 일부)를 탈 수 있다. 그러므로 두 역 사이를 이동하는 비용은, 한 역에서 다른 역까지 가기 위해 타야 하는 노선의 최소 개수(승차권 장수)와 같다.

서로 다른 두 역으로 이루어진 순서 없는 모든 쌍에 대해 이동 비용의 평균이 최소가 되도록 Bitwise 로 삼을 역을 정하여라.

첫째 줄에 역의 개수 $n$ ($2 \le n \le 1{,}000{,}000$) 이 주어진다. 역은 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 이어지는 $n-1$ 개의 줄에는 각각 선로 구간 하나가 두 정수 $a$ 와 $b$ ($1 \le a < b \le n$) 로 주어지며, 이는 $a$ 번 역과 $b$ 번 역이 직접 연결되어 있음을 뜻한다. 주어지는 철도망은 트리이다.

Bitwise 로 삼아야 하는 역의 번호, 즉 서로 다른 두 역의 모든 쌍에 대한 평균 이동 비용을 최소로 만드는 역의 번호를 정수 하나로 출력한다. 그런 역이 여러 개라면 그중 가장 작은 번호를 출력한다.

그림에서 원은 역(안의 숫자는 역 번호)이고, 선은 선로 구간이다. 이 철도망에서는 $7$ 번 역과 $8$ 번 역이 모두 최적의 허브이다. 동점일 때는 가장 작은 번호를 고르므로 답은 $7$ 이다. 둘 중 어느 쪽을 Bitwise 로 삼든, 서로 다른 두 역으로 이루어진 $28$ 개의 모든 쌍에 대한 평균 이동 비용은 $\frac{36}{28} \approx 1.2857$ 이다.