在玻维尼亚的土地上有 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 高兴的铺路。