题目描述

题目译自 XXX Olimpiada Informatyczna – III etap Park linowy

Bajtazar 买下了 Stubitowy 森林的一片土地，计划打造一个绳索公园。他选定了 $n$ 棵高耸的树，每棵树上将搭建一个木制平台。每个平台固定在树上，高度为从地面起的正整数（单位：米）。如何为每个平台选择合适的高度，让 Bajtazar 夜不能寐。唯一让他稍感安慰的是，这些树足够高，平台可安置在 $1$ 至 $n$ 米之间的任意整数高度。

Bajtazar 已规划了 $n-1$ 条绳索连接，链接各个平台。每条绳索允许双向通行，连接的两个平台间可通过一系列绳索往返。任意两个平台间均存在路径。

若两平台间有绳索连接，它们的的高度必须不同，否则通行会显得乏味。此外，对于部分绳索，Bajtazar 已指定了滑行和攀爬方向，即哪个平台必须高于另一个。

绳索公园所需的认证和检查数量与平台的最大高度成正比。因此，Bajtazar 希望找出最小的自然数 $M$，使得所有平台的高度不超过 $M$ 米时，他的计划仍可实现。

输入格式

第一行包含一个整数 $t\ (1 \leq t \leq 25000)$，表示数据组数。每组数据的格式如下：

每组输入数据的第一行包含一个整数 $n$ $(2 \leq n \leq 200000)$，表示树（及平台）的数量，树编号为 $1$ 至 $n$。
接下来的 $n-1$ 行描述绳索连接，第 $i$ 行包含三个整数 $a_i, b_i, d_i$ $(1 \leq a_i \neq b_i \leq n, 0 \leq d_i \leq 1)$，表示树 $a_i$ 和 $b_i$ 的平台间有绳索连接。两平台高度必须不同。若 $d_i=1$，则 $a_i$ 的平台必须低于 $b_i$ 的平台。

所有输入数据的 $n$ 值之和不超过 $200000$。

输出格式

对于每组输入数据，输出一行，包含一个整数 $M$，表示可实现计划的最小最大高度。

1
4
1 2 1
1 3 0
4 1 1

3

对于 $M=3$，一个可行的平台高度安排为：树 $1$ 的平台高度为 $2$，树 $2$ 为 $3$，树 $3$ 为 $1$ 或 $3$，树 $4$ 为 $1$。
当 $M \leq 2$ 时，不存在可行的平台高度安排。

附加样例

1. 单组输入数据，$n=1023=2^{10}-1$，对于每个 $k=1,2,\ldots,2^9-1$，平台 $k$ 必须低于平台 $2 \cdot k$，且与平台 $2 \cdot k + 1$ 高度不同，结果 $M=10$。
2. 单组输入数据，$n=50000$，每棵树最多有两条绳索连接。
3. 三组输入数据，$n$ 从 $[60000, 70000]$ 中随机抽取，每条绳索满足 $d_i=1$，连接平台 $1$ 与其他平台。

数据范围与提示

详细子任务附加限制及分值如下表所示。