Roads

Country X has $N$ towns, labelled with the numbers from $1$ to $N$. The road network consists of $N-1$ bidirectional regular roads. Each road connects two towns and has a fixed length, a positive integer. Every road was built at a different point in time. The network is designed so that between any two towns there is a route that uses regular roads only.

Car traffic keeps increasing, so the government plans to replace the regular roads with bidirectional highways. The highways are built by these rules.

• A highway is built only between a pair of towns that a direct road already connects. The highway replaces that regular road.
• Only a single highway is under construction at one point in time.
• The highways are built in the same order in which the corresponding direct roads were built.

An area is a maximal set of towns and regular roads (no highways) of the initial road network such that between any two towns in it there is a route that uses regular roads only. After each highway is built, exactly one area splits into two areas. One or both of the new areas may consist of a single town with no roads. A simple route is a route that passes through each town at most once.

Write a program that reports, after each new highway is built, the lengths of the longest simple routes between two towns in each of the two new areas.

The first line contains a single positive integer $N$, the number of towns in country X.

The next $N-1$ lines describe the road network before the construction of the highways. Each line holds three positive integers separated by spaces. The first two are the labels of the towns between which there is a regular road, and the third is its length.

The regular roads are given in the same order in which they were built.

Print $N-1$ lines. On line $i$, print two integers separated by a space: the lengths of the longest simple routes between two towns in each of the two new areas formed after the $i$-th highway is built. Such a route uses regular roads only. Print the two integers in nondecreasing order.

• $1 \le N \le 500000$
• The length of every regular road is between $1$ and $1000$, inclusive.

$\{t_1, t_2, \ldots, t_k\}$ denotes an area that contains the towns $t_1, t_2, \ldots, t_k$ and the regular roads between them. The walkthrough below follows the first example.

1. Before the first highway is built.

   

   There is only one area, $\{1, 2, 3, 4, 5\}$.

2. After the first highway is built between towns 1 and 2.

   

   The country splits into two areas, $\{1, 5\}$ and $\{2, 3, 4\}$. The lengths of the longest simple routes between two towns in them are 3 in $\{1, 5\}$ (between towns 1 and 5) and 3 in $\{2, 3, 4\}$ (between towns 3 and 4).

3. After the second highway is built between towns 2 and 3.

   

   The area $\{2, 3, 4\}$ splits into $\{3\}$ and $\{2, 4\}$. The lengths of the longest simple routes in the two areas are 0 and 2. Print these numbers in increasing order.

4. After the third highway is built between towns 2 and 4.

   

   The area $\{2, 4\}$ splits into $\{2\}$ and $\{4\}$. The lengths of the longest simple routes in both areas are 0.

5. After the fourth highway is built between towns 1 and 5.

   

   The area $\{1, 5\}$ splits into $\{1\}$ and $\{5\}$. The lengths of the longest simple routes are 0.