P10777 BZOJ3706 Inverting Brush

Given an undirected graph with $n$ vertices and $m$ edges, each edge is colored either black or white. You may perform several cycle color-inversion operations. In each operation, you start from any vertex, traverse edges, and for every edge you pass through, you invert its color. Finally, you return to the starting vertex. Determine whether it is possible, after some operations, to make all edges in the graph white. For some reason, edge colors can change. That is, you need to support the following two operations: - `1 x`: invert the color of the $x$-th edge (edges are numbered $0\sim m-1$); - `2`: query the minimum number of operations.

The first line contains two integers $n, m$, meaning the graph has $n$ vertices and $m$ edges. The next $m$ lines each contain three integers $u, v, c$, describing an undirected edge and its color, where $0$ means white and $1$ means black. Then an integer $q$ follows, meaning there are $q$ operations. The next $q$ lines contain the operations, as described above.

For each query, output one integer per line, representing the minimum number of color-inversion operations needed. If there is no valid solution, output $-1$.

Constraints: $1\leq n,m,q \leq 1000000$, $c < 2$, and there are no multiple edges or self-loops. Translated by ChatGPT 5