Problem Description

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.

Input Format

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.

Output Format

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.

2
3 7
3 6 1
2 6 0
2 5 1
3 5 1
1 6 1
3 4 0
1 5 1
3 7
1 6 1
3 5 1
2 5 1
3 4 1
1 5 0
1 4 0
2 6 0

5 3 6
-1

Hint

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