题目描述

给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \sim n$，右部点编号为 $n + 1 \sim 2n$。

给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。

如果你对二分图的定义有疑问：

• 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。
• 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。

输入格式

第一行一个正整数 $T$，表示数据组数。每组数据的格式如下：

第一行两个正整数 $n, m$，表示图的点数和边数。接下来 $m$ 行，每行三个整数 $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)$，表示一条连接 $u_i$, $v_i$ 的边，颜色为 $c_i$。$c_i = 0$ 表示白色，$c_i = 1$ 表示黑色。

输出格式

对于每组数据：如果无解，输出一行 $-1$。否则，输出一行 $n$ 个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为 $1 \sim m$。

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

提示

【样例解释】

在第一组数据中，一个合法的完美匹配是 $(1, 6),(2, 5),(3, 4)$，且里面有恰好两条黑色边。

在第二组数据中，虽然存在完美匹配，但每个完美匹配都有奇数条黑色边。

【数据范围】

本题使用子任务捆绑测试。

对于所有数据，保证 $1 \leq T \leq 250$，$2 \leq n,\sum n \leq 500$，$1 \leq m \leq n^2$。保证图中不存在重边，即对于 $i \neq j$ 有 $(u_i, v_i)\neq (u_j , v_j)$。

• Subtask 1（20%）：$n ≤ 8$，$T ≤ 10$。
• Subtask 2（20%）：$n ≤ 18$，$T ≤ 10$。
• Subtask 3（20%）：$c_i$ 在 $\{0, 1\}$ 里独立均匀随机。
• Subtask 4（40%）：无特殊限制。