문제
세계적으로 K-pop 열풍이 불고 있다. 당신은 K-pop 콘서트를 N개의 국가 중 한 곳에서 개최하려고 한다.
각 나라 사이에는 비행기로 이동할 수 있는 왕복항로가 N-1개 존재하고,
어느 두 국가를 정해도, 한 국가에서 다른 국가까지 가는 방법은 정확히 한 가지 있다.
K-pop 콘서트를 개최한 이후, K-pop 콘서트를 보고 다시 자국으로 돌아가려는 사람들로 북적일 것이다.
K-pop 콘서트가 끝나고 생기는 공항의 혼잡을 줄이기 위해, 혼잡 점수를 최소가 되게 하려고 한다.
이 때, 혼잡 점수는 사람이 가장 많이 지나가는 항로의 사람 수와 같다.
이 때, N과 각 국가에서 K-pop 콘서트를 볼 사람들의 수가 주어질 때,
혼잡 점수가 최소가 되게 K-pop 콘서트의 개최 위치를 정하는 프로그램을 작성하여라.
모든 사람의 수가 20억을 넘지 않는다.
[입력 예 그림 설명]
입력
첫 번째 줄에는 국가의 수 N(1≤N≤1,000,000)이 주어진다. 두 번째 줄에는 각 국가에서 K-pop 콘서트를 볼 사람들의 수가 주어진다. 다음 줄에서부터 N-1개의 줄에는 각 국가 간의 항로가 주어진다. 이 때, 국가 번호는 0 이상 N-1 이하이다.
출력
K-pop 콘서트를 개최하는 국가의 번호를 출력한다. 답이 여러 개이면 그 중 아무거나 출력한다.
예제1
입력
5
1010102020
02
12
32
43
출력
3
출처
IOI 2010 Day2