P10080 [GDKOI2024 Senior] Matching

You are given a bipartite graph with $2n$ vertices and $m$ edges. The left part vertices are numbered $1 \sim n$, and the right part vertices are numbered $n + 1 \sim 2n$. Each edge is colored black or white. You need to find a perfect matching such that the number of black edges in the matching is exactly even. If you are unsure about the definition of a bipartite graph: - A bipartite graph is an undirected graph whose vertices are divided into two parts, left and right, with $n$ vertices in each part. Every edge connects two vertices from different parts. - A perfect matching is a set of $n$ edges such that every vertex is incident to exactly one edge in the set.

The first line contains a positive integer $T$, indicating the number of test cases. Each test case is as follows: The first line contains two positive integers $n, m$, indicating the number of vertices and the number of edges. The next $m$ lines each contain three integers $u_i, v_i, c_i(1 \leq u_i \leq n, n+1 \leq v_i \leq 2n, 0 \leq c_i \leq 1)$, describing an edge connecting $u_i$ and $v_i$ with color $c_i$. Here, $c_i = 0$ means white, and $c_i = 1$ means black.

For each test case: if there is no solution, output a line containing $-1$. Otherwise, output a line of $n$ positive integers, indicating the indices of the edges in the perfect matching you found. Edges are numbered $1 \sim m$ in the input order.

**Sample Explanation** In the first test case, one valid perfect matching is $(1, 6),(2, 5),(3, 4)$, and it contains exactly two black edges. In the second test case, although a perfect matching exists, every perfect matching has an odd number of black edges. **Constraints** **This problem uses bundled subtasks.** For all testdata, it is guaranteed that $1 \leq T \leq 250$, $2 \leq n,\sum n \leq 500$, $1 \leq m \leq n^2$. It is guaranteed that there are no multiple edges in the graph, i.e., for $i \neq j$, $(u_i, v_i)\neq (u_j , v_j)$. - Subtask 1 (20%): $n \leq 8$, $T \leq 10$. - Subtask 2 (20%): $n \leq 18$, $T \leq 10$. - Subtask 3 (20%): $c_i$ are independently and uniformly random in $\{0, 1\}$. - Subtask 4 (40%): No special constraints. Translated by ChatGPT 5