题目描述
有一个由 $n$ 座城市构成的国家，其城市之间将由 $m$ 条双向道路互相连接，第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$；但由于工程延期，第 $i$ 条道路只在第 $\boldsymbol{w_i}$ 天及以后开放。保证这些双向道路两两不同，每条道路连接两个不同的城市，且在所有道路开放后，从城市 $1$ 出发可以到达其余所有城市。
每座城市都设有若干街灯，用于夜间照明。每个夜晚降临后，每位点灯人仅点亮自己所在城市的灯；而日出后，点灯人又会熄灭自己所在城市的灯。初始时，有充分多的点灯人在城市 $1$。这被记作第 $0$ 夜。
为了给国家的每座城市照明，每位点灯人必须在每天白天沿城市之间的道路移动。具体地，对每个正整数 $t$，设第 $t-1$ 夜某位点灯人在城市 $x$，则他在第 $t$ 天必须沿着某条一端为城市 $x$ 且已经开放（即 $w$ 值不超过 $t$）的道路，随后恰好在第 $t$ 夜到达道路的另一个端点。如果有多条不同的道路，则每位点灯人会独立地随机选择一条；特别地，如果这样的道路不存在，则这位点灯人会失望地离开这个国家。
你想知道是否存在一个非负整数 $d$，满足在第 $d$ 夜，所有城市内的灯都被点亮；换句话说，在第 $d$ 夜，每个城市内都存在至少一位点灯人。如果存在，你还希望找到符合条件的最小可能的 $d$。
出于某些原因，给定一个参数 $o \in \{0, 1\}$，你只需要在 $d$ 存在时输出 $o \cdot d$ 的值即可。
输入格式
本题有多组测试数据。
第一行，两个整数 $c, T$，分别表示测试点编号与测试数据组数。接下来输入每组测试数据。样例满足 $c = 0$。
对于每组测试数据：
- 第一行，三个正整数 $n$，$m$ 和 $o$，分别表示城市数量，道路数量，和给定的参数。
- 接下来 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i, w_i$。
保证这些双向道路两两不同，每条道路连接两个不同的城市，且在所有道路开放后，从城市 $1$ 出发可以到达其余所有城市。
输出格式
对于每组测试数据，输出一行一个整数：
- 若存在满足条件的非负整数 $d$，则输出满足条件的最小可能的 $d$ 与 $o$ 的乘积；
- 若不存在满足条件的非负整数 $d$，输出 $-1$。
样例 1 输入
0 2 4 4 1 2 1 2 1 3 1 1 4 1 3 4 2 3 2 1 1 2 2 1 3 3
样例 1 输出
3 -1
样例 1 解释
对于第一组测试数据：
- 在第 $0$ 夜，只有第 $1$ 个城市存在充分多的点灯人，灯亮的城市为第 $1$ 个城市。
- 在第 $1$ 天，第 $1$ 个城市的点灯人全部移动至城市 $3$ 和 $4$。注意，点灯人不能移动到城市 $2$，因为道路 $(1, 2)$ 在第 $w = 2$ 天后才建设完成。因此，在第 $1$ 夜，灯亮的城市为第 $3, 4$ 个城市；由于点灯人数量充分多，所以必然有一些点灯人到达城市 $3$，而另外一些点灯人到达城市 $4$。
- 在第 $2$ 天，第 $3$ 个城市的点灯人全部移动到城市 $1, 4$，而第 $4$ 个城市的点灯人全部移动到城市 $1, 3$。因此，在第 $2$ 夜，灯亮的城市有第 $1, 3, 4$ 个城市。
- 在第 $3$ 天，第 $1$ 个城市的点灯人全部移动到城市 $2, 3, 4$，第 $3$ 个城市的点灯人全部移动到城市 $1, 4$，而第 $4$ 个城市的点灯人全部移动到城市 $1, 3$。因此，在第 $3$ 夜，所有城市的灯都被点亮。
因此，$d = 3$，输出 $o \cdot d$ 即 $3$。
对于第二组测试数据，在第 $1$ 天，城市 $1$ 邻接的所有道路都未开放，因此所有点灯人都无法移动，他们会离开这个国家。因此，不存在符合条件的非负整数 $d$，输出 $-1$。
样例 2
见附件中的 $\textit{lamplighter/lamplighter2.in}$ 与 $\textit{lamplighter/lamplighter2.ans}$。
该组样例满足测试点 $1 \sim 2$ 的约束条件。
样例 3
见附件中的 $\textit{lamplighter/lamplighter3.in}$ 与 $\textit{lamplighter/lamplighter3.ans}$。
该组样例满足测试点 $3 \sim 4$ 的约束条件。
样例 4
见附件中的 $\textit{lamplighter/lamplighter4.in}$ 与 $\textit{lamplighter/lamplighter4.ans}$。
该组样例满足测试点 $7 \sim 8$ 的约束条件。
样例 5
见附件中的 $\textit{lamplighter/lamplighter5.in}$ 与 $\textit{lamplighter/lamplighter5.ans}$。
该组样例满足测试点 $12 \sim 14$ 的约束条件。
样例 6
见附件中的 $\textit{lamplighter/lamplighter6.in}$ 与 $\textit{lamplighter/lamplighter6.ans}$。
该组样例满足测试点 $15 \sim 16$ 的约束条件。
样例 7
见附件中的 $\textit{lamplighter/lamplighter7.in}$ 与 $\textit{lamplighter/lamplighter7.ans}$。
该组样例满足测试点 $17 \sim 19$ 的约束条件。
样例 8
见附件中的 $\textit{lamplighter/lamplighter8.in}$ 与 $\textit{lamplighter/lamplighter8.ans}$。
该组样例满足测试点 $22 \sim 25$ 的约束条件。
数据范围
本题共 $25$ 个测试点，每个 $4$ 分。
对于所有数据，保证：
- $1 \leq T \leq 10$；
- $2 \leq n \leq 2.5\times 10^4$；
- $n - 1 \leq m \leq 5\times 10^4$；
- $o \in \{0, 1\}$；
- 对所有 $1 \leq i \leq m$，$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$，$1 \leq w_i \leq 10^9$；
- 保证双向道路两两不同；
- 保证在所有道路开放后，从城市 $1$ 出发可以到达其余所有城市。
| 测试点编号 | $n \leq$ | $m \leq$ | $o = $ | 特殊性质 |
|---|---|---|---|---|
| $1 \sim 2$ | $10$ | $20$ | $1$ | A |
| $3 \sim 4$ | $10^3$ | $2\times 10^3$ | $1$ | B |
| $5 \sim 6$ | $10^3$ | $2\times 10^3$ | $0$ | 无 |
| $7 \sim 8$ | $10^3$ | $2\times 10^3$ | $1$ | 无 |
| $9 \sim 11$ | $2.5\times 10^4$ | $5\times 10^4$ | $0$ | B |
| $12 \sim 14$ | $2.5\times 10^4$ | $5\times 10^4$ | $0$ | 无 |
| $15 \sim 16$ | $2.5\times 10^4$ | $5\times 10^4$ | $1$ | B |
| $17 \sim 19$ | $10^4$ | $2\times 10^4$ | $1$ | C |
| $20 \sim 21$ | $2.5\times 10^4$ | $5\times 10^4$ | $1$ | C |
| $22 \sim 25$ | $2.5\times 10^4$ | $5\times 10^4$ | $1$ | 无 |
- 特殊性质 A：保证 $w_i \leq 2\times 10^5$。
- 特殊性质 B：保证 $w_i$ 全部相等。
- 特殊性质 C：保证非负整数 $d$ 存在。