CF603E Pastoral Oddities

在 Bovinia 之地有 $n$ 个牧场，但是没有任何路径连接这些牧场。当然，这是个糟糕的状况，所以 Kevin Sun 计划修建 $m$ 条无向路径，每条路径连接两个不同的牧场。为了让交通更加高效，他还打算对这些新建的路径进行铺设。 Kevin 对铺设的某些方面有独特的要求。因为他喜欢奇数，他希望每个牧场正好连接奇数条已铺设的路径。因此，我们称一次铺设是“阳光铺设”（sunny）当且仅当每个牧场都恰好与奇数条已铺设路径相连。同时，他更喜欢较短的路径，不喜欢长路径，因此他希望在满足“阳光铺设”的条件下，被铺设路径中最长的那条路径长度要尽可能短。每修建一条新路径后，Kevin 想知道当前能否存在“阳光铺设”，若存在，输出满足条件下被铺设路径中最长的那条路径的最小可能长度。注意，这里的“最长路径”指的是所有被铺设路径中长度最大的一条路径。 #

第一行包含两个整数 $n$（$2 \le n \le 100000$）和 $m$（$1 \le m \le 300000$），表示牧场数和路径数。接下来的 $m$ 行，每行包含三个整数 $a_{i}$、$b_{i}$ 和 $l_{i}$，描述第 $i$ 条路径：第 $i$ 条路径连接牧场 $a_{i}$ 和 $b_{i}$（$1 \le a_{i}, b_{i} \le n$，$a_{i} \neq b_{i}$），长度为 $l_{i}$（$1 \le l_{i} \le 10^{9}$）。路径按照修建顺序给出。 #

输出 $m$ 行，第 $i$ 行表示在建成前 $i$ 条路径后，如果 Kevin 可以选择一些路径进行铺设，使得每个牧场都正好连接奇数条铺设过的路径，则输出所有被铺设路径中最大长度的最小可能值，否则输出 $-1$。 注意，铺设是“假想”的——你的第 $i$ 次输出不应受到前面任意回答的影响。 #

对于第一个样例，Kevin 每次修建完前 $i$ 条路径后应选择铺设的路径如下： 1. 没有可能的路径集合满足条件。 2. 铺设第 1 条（长度 $4$）和第 2 条（长度 $8$）路径。 3. 铺设第 1 条（长度 $4$）和第 2 条（长度 $8$）路径。 4. 铺设第 3 条（长度 $2$）和第 4 条（长度 $3$）路径。 对于第二个样例，始终不存在使 Kevin 满意的铺设方案。 由 ChatGPT 5 翻译