Towns

Kazakhstan has $N$ small towns numbered from 0 through $N-1$. It also has some number of large cities, and the count is not given. Small towns and large cities together are called settlements.

All settlements are connected by one network of bidirectional highways. Each highway connects two distinct settlements, and each pair of settlements is joined by at most one highway. For any two settlements $a$ and $b$, there is exactly one way to travel from $a$ to $b$ without using any highway more than once.

Each small town is directly connected to exactly one other settlement. Each large city is directly connected to three or more settlements.

Every highway has a positive integer length. The distance between two settlements is the smallest total length of highways needed to travel between them.

For a large city $C$, let $r(C)$ be the distance from $C$ to the small town farthest from $C$. A large city is a hub if its $r(C)$ is the smallest among all large cities. $R$ is the smallest value of $r(C)$, which is the distance from a hub to the small town farthest from it.

In the figure, city $f$ is the only hub, with $r(f) = 16$, so $R = 16$. Removing $f$ splits the network into four pieces containing the small town sets {0, 1, 10}, {2, 3}, {4, 5, 6, 7}, and {8, 9}. No piece has more than $\lfloor 11/2 \rfloor$ small towns, so $f$ is a balanced hub.

Removing a hub splits the network into several connected pieces. A hub is balanced if each piece contains at most $\lfloor N/2 \rfloor$ small towns. Large cities are not counted.

$6 \le N \le 110$.

The distance between any two distinct small towns is between 1 and 1,000,000 inclusive.

The number of queries your program may make is limited. The limit varies by subtask. If the program exceeds the query limit, it is terminated and the answer is judged incorrect.