Pastoral Oddities
Contest: Codeforces Round 334 (Div. 1)
Difficulty rating: 3000
Tags: data structures, divide and conquer, dsu, math, trees

In the land of Bovinia there are n pastures, but no paths connecting the pastures. Of course, this is a terrible situation, so Kevin Sun is planning to rectify it by constructing m undirected paths connecting pairs of distinct pastures. To make transportation more efficient, he also plans to pave some of these new paths.

Kevin is very particular about certain aspects of path-paving. Since he loves odd numbers, he wants each pasture to have an odd number of paved paths connected to it. Thus we call a paving sunny if each pasture is incident to an odd number of paved paths. He also enjoys short paths more than long paths, so he would like the longest paved path to be as short as possible. After adding each path, Kevin wants to know if a sunny paving exists for the paths of Bovinia, and if at least one does, the minimum possible length of the longest path in such a paving. Note that "longest path" here means maximum-weight edge.

Input format:
The first line contains two integers n (2 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 300 000), denoting the number of pastures and paths, respectively. The next m lines each contain three integers ai, bi and li, describing the i-th path. The i-th path connects pastures ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) and has length li (1 ≤ li ≤ 109). Paths are given in the order in which they are constructed.

Output format:
Output m lines. The i-th line should contain a single integer denoting the minimum possible length of the longest path (maximum-weight edge) in a sunny paving using only the first i paths. If Kevin cannot pave a set of paths so that each pasture is incident to an odd number of paved paths, output  - 1.

Note that the paving is only hypothetical—your answer after adding the i-th path should not be affected by any of your previous answers.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
For the first sample, these are the paths that Kevin should pave after building the i-th path:

1. No set of paths works.
2. Paths 1 (length 4) and 2 (length 8).
3. Paths 1 (length 4) and 2 (length 8).
4. Paths 3 (length 2) and 4 (length 3).

In the second sample, there never exists a paving that makes Kevin happy.

Example input:
4 4
1 3 4
2 4 8
1 2 2
3 4 3

Example output:
-1
8
8
3

Example input:
3 2
1 2 3
2 3 4

Example output:
-1
-1

Editorial:
Hint: What is a necessary and sufficient condition for Kevin to be able to pave paths so that each edge is incident to an odd number of them? Does this problem remind you of constructing a minimum spanning tree?
We represent this problem on a graph with pastures as vertices and paths as edges. Call a paving where each vertex is incident to an odd number of paved edges an odd paving. We start with a lemma about such pavings:
A connected graph has an odd paving if and only if it has an even number of vertices.
For connected graphs with even numbers of vertices, we can prove this observation by considering a spanning tree of the graph. To construct an odd paving, start from the leaves of the tree and greedily pave edges so that each vertex but the root is incident to an odd number of paved edges. Now consider the graph consisting only of paved edges. Since the sum of all vertex degrees in this graph must be even, it follows that the root is also incident to an odd number of paved edges, so the paving is odd.
Now we prove that no odd paving exists in the case of an odd number of vertices. Suppose for the sake of contradiction that one existed. Then the sum of the vertex degrees in the graph consisting only of paved edges would be odd, which is impossible. Thus no odd paving exists for graphs with odd numbers of vertices.
Note that this observation turns the degree condition into a condition on the parity of connected component sizes. We finish the problem using this equivalent condition.
Suppose we only want to solve this problem once, after all m edges are added. Then we can use Kruskal's algorithm to build a minimum spanning forest by adding edges in order of increasing length. We stop once each tree in the forest contains an even number of vertices, since the graph now satisfies the conditions of the lemma. If there are still odd-sized components by the time we add all the edges, then no odd paving exists. This algorithm, however, runs in $${ \mathcal { O } } ( m \log m )$$ per query, which is too slow if we want to answer after adding each edge.
To speed things up, we maintain the ending position of our version of Kruskal's as we add edges online. We do this using a data structure called a link-cut tree. This data structure allows us to add and delete edges from a forest while handling path and connectivity queries. All of these operations take only $${\mathcal {O}}(\log n)$$ time per operation. (A path query asks for something like maximum-weight edge on the path between u and v; a connectivity query asks if u and v are connected.)
First, let's look at how we can solve the online minimum spanning tree problem with a link-cut tree. We augment our data structure to support finding the maximum-weight edge on the path between vertices u and v in $${\mathcal {O}}(\log n)$$. Adding an edge then works as follows: If u and v are not connected, connect u and v; otherwise, if the new edge is cheaper, delete the maximum-weight edge on the path between u and v and add the new edge. To make implementation easier, we can represent edges as vertices in the link-cut tree. For example, if u and v are connected, in the link-cut tree they would be connected as u–e–v, where e is a vertex representing edge u–v.
We solve our original problem with a similar idea. Note that the end state of our variation on Kruskal's is a minimum spanning forest after adding k edges. (We no longer care about the edges that are longer than the longest of these k edges, since the answer is monotonically decreasing—more edges never hurt.) So when we add another edge to the forest, we can use the online minimum spanning tree idea to get the minimum spanning forest that uses the old cheapest k edges and our new edge. Note that inserting the edge never increases the number of odd components: even linked to even is even, even linked to odd is odd, odd linked to odd is even.
Now, pretend that we got this arrangement by running Kruskal's algorithm, adding the edges one-by-one. We can "roll back" the steps of the algorithm by deleting the longest edge until deleting another edge would give us an odd-sized component. (If we started with an odd-sized component, we don't delete anything.) This gives us an ending position for our Kruskal-like algorithm that uses a minimal number of edges so that all components have even size—we're ready to add another edge. ("But wait a minute!" you may say. "What if edges have the same weight?" In this case, if we can't remove one of possibly many longest edges, then we can't lower our answer anyway, so we stop.)
Note that all of this takes amortized $${\mathcal {O}}(\log n)$$ time per edge. The path queries and the insertion of the new edge involve a constant number of link-cut tree operations. To know which edge to delete, the set of edges currently in the forest can be stored easily in an STL set sorted by length. When adding an edge, we also pay for the cost of deleting that edge, so the "rolling back" phase gets accounted for. Therefore, this algorithm runs in $${\mathcal {O}}(m\log n)$$.
You may have noticed that executing this algorithm involves checking the size of a connected component in the link-cut tree. This is a detail that needs to be resolved carefully, since link-cut trees usually only handle path operations, not operations that involve subtrees. Here, we stop treating link-cut trees as a black box. (If you aren't familiar with the data structure, you should read about it athttps://courses.csail.mit.edu/6.851/spring12/scribe/L19.pdf.) At each vertex, we track the size of its virtual subtree, as well as the sum of the real subtree sizes of its non-preferred children. We can update these values while linking and exposing (a.k.a. accessing), allowing us to perform root-change operations while keeping real subtree sizes. To get the size of a component, we just query for the real subtree size of the root.
Since the implementation of this algorithm can be rather challenging, here is a link to a documented version of my code:coming soon to a text editor near you