← 返回题目列表

Codeforces · 603/E

E. 田园奇事

中文机器翻译题面 查看原题

在玻维尼亚的土地上有 n 个牧场,但没有连接牧场的路径。当然,这是一个可怕的情况,因此 Kevin Sun 计划通过构建 m 条连接不同牧场的无向路径来纠正这种情况。为了提高交通效率,他还计划铺设一些新道路。

凯文对于铺路的某些方面非常讲究。由于他喜欢奇数,因此他希望每个牧场都有奇数条铺砌的道路与其相连。因此,如果每个牧场都有奇数条铺砌路径,我们就称铺砌阳光充足。与长路相比,他更喜欢短路,因此他希望最长的铺砌路越短越好。添加每条路径后,Kevin 想知道 Bovinia 的路径是否存在阳光明媚的铺路,如果至少有一条,则此类铺路中最长路径的最小可能长度。请注意,这里的“最长路径”意味着最大权重边。

输入

第一行包含两个整数n(2≤n≤100000)和m(1≤m≤300000),分别表示牧场和路径的数量。接下来的 m 行每行包含三个整数 ai、bi 和 li,描述第 i 条路径。第 i 条路径连接牧场 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),长度为 li (1 ≤ li ≤ 109)。路径按其构造顺序给出。

输出

输出 m 行。第 i 行应包含一个整数,表示仅使用前 i 条路径的阳光明媚铺路中最长路径(最大权重边缘)的最小可能长度。如果 Kevin 无法铺设一组路径以使每个牧场都与奇数条铺设路径相关,则输出 - 1。

请注意,铺路只是假设 - 添加第 i 条路径后的答案不应受到之前任何答案的影响。

示例

输入 #1

4 4
1 3 4
2 4 8
1 2 2
3 4 3

输出 #1

-1
8
8
3

输入 #2

3 2
1 2 3
2 3 4

输出 #2

-1
-1

输入 #3

4 10
2 1 987
3 2 829
4 1 768
4 2 608
3 4 593
3 2 488
4 2 334
2 1 204
1 3 114
1 4 39

输出 #3

-1
-1
829
829
768
768
768
488
334
204

注意

对于第一个示例,这些是 Kevin 在构建第 i 条路径后应铺设的路径:

1. 没有一组路径有效。
2. 路径 1(长度 4)和 2(长度 8)。
3. 路径 1(长度 4)和 2(长度 8)。
4. 路径 3(长度 2)和 4(长度 3)。

在第二个示例中,从来不存在让 Kevin 高兴的铺路。