markdown

E. 牧场的奇偶铺设

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $256$ 兆字节
输入：标准输入
输出：标准输出

在 Bovinia 这片土地上有 $n$ 个牧场，但牧场之间没有任何道路相连。这显然很不方便，因此 Kevin Sun 计划修建 $m$ 条无向道路，连接不同的牧场对，以改善这一状况。为了让交通更高效，他还打算铺设其中的一些新道路。

Kevin 对道路铺设有一些特殊要求。他非常喜欢奇数，因此他希望每个牧场都与奇数条铺设过的道路相连。我们称一种铺设方案为“晴好铺设”，当且仅当每个牧场都与奇数条铺设过的道路相连。此外，比起长道路，他更喜欢短道路，因此他希望铺设的道路中最长的那条尽可能短。在每添加一条新道路后，Kevin 都想知道：是否存在一种晴好铺设方案？如果存在，那么在这种铺设方案中，最长道路的最小可能长度是多少。注意，这里的“最长道路”指的是边权最大的那条边。

输入格式

第一行包含两个整数 $n$（$2 \le n \le 100\,000$）和 $m$（$1 \le m \le 300\,000$），分别表示牧场的数量和待修建的道路数量。
接下来的 $m$ 行中，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $l_i$，描述第 $i$ 条道路。第 $i$ 条道路连接牧场 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），长度为 $l_i$（$1 \le l_i \le 10^9$）。道路按照修建的顺序给出。

输出格式

输出 $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

注释

对于第一个样例，在修建第 $i$ 条道路后，Kevin 应该铺设的道路如下：

• 没有任何道路可行。
• 道路 $1$（长度 $4$）和道路 $2$（长度 $8$）。
• 道路 $1$（长度 $4$）和道路 $2$（长度 $8$）。
• 道路 $3$（长度 $2$）和道路 $4$（长度 $3$）。

在第二个样例中，始终不存在能让 Kevin 满意的铺设方案。