Cycle Flipping Puzzle

You are given an undirected graph with n vertices and m edges. Each edge is colored either black or white. You are allowed to perform a series of cycle flipping operations. In one such operation, you can start at any vertex and traverse a simple cycle (i.e. a closed path in which no edge is repeated) – upon traversing each edge, its color is flipped (black becomes white, white becomes black). The goal is to determine whether it is possible, by performing several (possibly zero) cycle flipping operations, to turn all edges white. If it is possible, you must also find the minimum number of cycle operations needed.

There is a twist, however. For some reason, the colors of the edges can change dynamically. Hence, aside from the cycle flipping operations described above, you need to support the following two types of operations:

• 1 x — flip the color of the x-th edge (edges are numbered from 0 to m-1). This operation toggles the color of the specified edge.
• 2 — output the minimum number of cycle flipping operations required to turn all edges white on the current graph configuration. If it is impossible, output -1.
</p>

Important Details

• An operation of type 2 requires you to consider only cycle flipping operations. Note that a single cycle flipping operation must correspond to a simple cycle (i.e. it must not repeat any edge) that, when traversed, flips each traveled edge exactly once.
• The cycle flipping operation is valid only if the set of black edges (represented as 1) forms an Eulerian subgraph, meaning every vertex has an even degree (i.e. an even count of incident black edges). Hence, if at least one vertex has an odd number of black incident edges, it is impossible to convert all edges to white using cycle operations, and your answer should be -1.
• If the black subgraph is Eulerian, then note that each connected component of black edges has an Eulerian circuit. Since a cycle operation can only operate on a single connected component, the minimum number of cycle flipping operations required is exactly the number of connected components in the subgraph induced by black edges (ignoring isolated vertices). In the case where there are no black edges at all, the answer is 0.

Input and output format details are provided below.

inputFormat

The input begins with two integers n and m — the number of vertices and edges, respectively.

Then follow m lines, each containing three integers u v c representing an edge between vertices u and v with initial color c (where c = 0 stands for white and c = 1 for black). Vertices are numbered from 0 to n-1.

The next line contains an integer Q — the number of operations.

Each of the next Q lines is either in one of the following formats:

• 1 x — flip the color of the x-th edge.
• 2 — query the minimum number of cycle flipping operations required to turn all edges white on the current graph.

outputFormat

For each operation of type 2, output a single integer on a separate line: the minimum number of cycle flipping operations required to turn all edges white, or -1 if it is impossible.

sample

3 3
0 1 1
1 2 1
2 0 1
1
2

1

</p>