Station

Time limit1sMemory limit128 MB

Summary

Pick a tree vertex as the hub so that the average number of hub-to-vertex paths needed to travel between unordered pairs of vertices is minimized.

Level: Medium7 of 10
Topics: Tree, DFS, Combinatorics, Greedy
Solved: No attempts yet

Problem

Byteotia's railway network consists of bidirectional track segments connecting railway stations. No two stations are directly connected by more than one segment, and every station is reachable from every other station along exactly one simple route. In other words, the network forms a tree.

The next stage of the reform organizes train lines around a single central station. Exactly one station is chosen to become a giant hub named Bitwise. For every other station, a line is set up that runs between Bitwise and that station along the unique route between them, stopping at every station in between. So there are $n-1$ lines in total.

Tickets are one-way and single-use. A single ticket lets a passenger ride one whole line (or any part of it), no matter how many track segments that line spans. The cost of traveling between two stations is therefore the minimum number of lines (tickets) a passenger must ride to get from one station to the other.

Choose which station becomes Bitwise so that the average travel cost, taken over all unordered pairs of two distinct stations, is as small as possible.

Input

The first line contains one integer $n$ ( $2 \le n \le 1{,}000{,}000$ ), the number of railway stations. Stations are numbered from $1$ to $n$ . Each of the next $n-1$ lines describes one track segment with two integers $a$ and $b$ ( $1 \le a < b \le n$ ), meaning stations $a$ and $b$ are directly connected. The described network is a tree.

Output

Print a single integer: the number of the station that should become Bitwise, that is, a station that minimizes the average travel cost over all unordered pairs of distinct stations. If several stations attain this minimum, print the smallest such station number.

Hint

In the figure, circles are stations (the number inside each is its station number) and edges are track segments. Both station $7$ and station $8$ are optimal hubs; because ties are broken by choosing the smallest station number, the answer for this network is $7$ . With either of them as Bitwise, the average travel cost over all $28$ unordered pairs of distinct stations is $\frac{36}{28} \approx 1.2857$ .

Examples4

Example 1
Input
```
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
```
Expected output
```
7
```
Example 2
Input
```
2
1 2
```
Expected output
```
1
```
Example 3
Input
```
5
1 2
2 3
3 4
4 5
```
Expected output
```
1
```
Example 4
Input
```
6
1 2
1 3
1 4
1 5
1 6
```
Expected output
```
2
```