题目描述

在国家 X 中有 $N$ 个城镇，编号为 $1$ 到 $N$。公路网络由 $N-1$ 条双向普通道路组成，每条道路连接两个城镇，并且具有一个固定的正整数长度。所有这些道路的修建时间两两不同，并且整个道路网络满足：任意两个城镇之间都存在一条路线，这条路线要么是一条直接道路，要么经过若干城镇并只使用普通道路。

由于汽车交通不断增长，政府计划把这些普通道路逐条替换为双向高速公路。高速公路的修建遵循以下规则：

• 只有原本就有一条直接普通道路连接的两个城镇之间，才会修建高速公路；
• 高速公路会直接替换对应的普通道路；
• 任意时刻只会有一条高速公路在施工；
• 高速公路的修建顺序与原先普通道路的修建顺序完全相同。

我们称国家中的一个区域为：在初始道路网络中，一个由城镇和普通道路（不含高速公路）组成的极大连通子集，并且其中任意两个城镇之间都可以只通过普通道路互相到达。

每修建一条高速公路，国家中恰好有一个区域会被分裂成两个新的区域（其中一个或两个新区域都可能只是一个没有道路的单独城镇）。

一条简单路线是指经过任意城镇都不超过一次的路线。

在每修建完一条新的高速公路后，政府希望知道：新产生的两个区域中，各自内部两座城镇之间的最长简单路线长度是多少。

请编写程序 roads 来回答这些问题。

输入格式

第一行输入一个正整数 $N$，表示国家 X 中城镇的数量。

接下来 $N-1$ 行描述初始的普通道路网络。每行给出三个正整数，前两个表示一条普通道路连接的两个城镇编号，第三个表示这条道路的长度。

这些普通道路在输入中给出的顺序，就是它们当初修建的顺序。

输出格式

输出共 $N-1$ 行。

第 $i$ 行输出两个整数，表示修建第 $i$ 条高速公路之后，形成的两个新区域中，各自最长简单路线的长度。两个整数需按非递减顺序输出。

数据范围

• $1 \le N \le 500000$
• 所有普通道路的长度都在 $[1,1000]$ 范围内。

子任务与评分

子任务	分值	范围
1	9	$2 \le N \le 100$
2	21	$100 < N \le 2000$
3	11	$2000 < N \le 10000$
4	27	$10000 < N \le 100000$
5	32	$100000 < N \le 500000$

只有当某个子任务中的所有测试点全部通过时，才能获得该子任务的分数。

样例

输入

5
1 2 2
2 3 1
2 4 2
1 5 3

输出

3 3
0 2
0 0
0 0

样例解释

我们用 $\{t_1,t_2,\ldots,t_k\}$ 表示一个区域，它包含城镇 $t_1,t_2,\ldots,t_k$ 以及它们之间仍然保留的普通道路。

说明：原题样例解释配有 5 幅必不可少的示意图，分别展示初始状态以及每次修建高速公路后的道路网络变化。
你后续补图时，建议按下面 1-5 的位置插入对应图片。

1. 修建第一条高速公路之前

此时整个国家中只有一个区域：$\{1,2,3,4,5\}$。

2. 修建第一条高速公路（连接城镇 1 和 2）之后

国家被分成两个区域：$\{1,5\}$ 和 $\{2,3,4\}$。
它们内部两点间最长简单路线的长度分别为：

• 在 $\{1,5\}$ 中为 $3$（城镇 1 到城镇 5）；
• 在 $\{2,3,4\}$ 中为 $3$（城镇 3 到城镇 4）。

因此第一行输出为 3 3。

3. 修建第二条高速公路（连接城镇 2 和 3）之后

区域 $\{2,3,4\}$ 被分裂成两个区域：$\{3\}$ 和 $\{2,4\}$。
这两个区域中的最长简单路线长度分别为 $0$ 和 $2$。

注意要按升序输出，因此第二行输出为 0 2。

4. 修建第三条高速公路（连接城镇 2 和 4）之后

区域 $\{2,4\}$ 被分裂成两个区域：$\{2\}$ 和 $\{4\}$。
这两个区域中的最长简单路线长度都为 $0$。

因此第三行输出为 0 0。

5. 修建第四条高速公路（连接城镇 1 和 5）之后

区域 $\{1,5\}$ 被分裂成 $\{1\}$ 和 $\{5\}$。
最长简单路线长度都为 $0$。

因此第四行输出为 0 0。