Given a bipartite graph with $2n$ vertices and $m$ edges, where the left partition vertices are numbered $1 \sim n$ and the right partition vertices are numbered $n+1 \sim 2n$.

Each edge is either black or white. You need to find a perfect matching such that the number of black edges in the matching is even.

If you have questions about the definition of a bipartite graph: A bipartite graph is an undirected graph where vertices are divided into two parts, each containing $n$ vertices, and every edge connects two vertices belonging to different parts. A perfect matching is a set of $n$ edges such that every vertex is connected to exactly one edge in the set.

Input

The first line contains a positive integer $T$, representing the number of test cases. The format for each test case is as follows:

The first line contains two positive integers $n, m$, representing the number of vertices and edges in the graph. The next $m$ lines each contain three integers $u_i, v_i, c_i$ ($1 \le u_i \le n, n+1 \le v_i \le 2n, 0 \le c_i \le 1$), representing an edge connecting $u_i$ and $v_i$ with color $c_i$. $c_i = 0$ represents white, and $c_i = 1$ represents black.

Output

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

Examples

Input 1

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

Output 1

5 3 6
-1

Note

In the first test case, a valid perfect matching is $(1, 6), (2, 5), (3, 4)$, which 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 subtask-based testing.

For all data, it is guaranteed that $1 \le T \le 250$, $2 \le n$, $\sum n \le 500$, $1 \le m \le 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 \le 8, T \le 10$
• Subtask 2 (20%): $n \le 18, T \le 10$
• Subtask 3 (20%): $c_i$ are chosen independently and uniformly at random from $\{0, 1\}$.
• Subtask 4 (40%): No special restrictions.