{"raw_statement":[{"iden":"statement","content":"给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \\sim n$，右部点编号为 $n + 1 \\sim 2n$。\n\n给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。\n\n如果你对二分图的定义有疑问：\n\n- 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。\n- 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。"},{"iden":"input","content":"第一行一个正整数 $T$，表示数据组数。每组数据的格式如下：\n\n第一行两个正整数 $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$ 表示黑色。"},{"iden":"output","content":"对于每组数据：如果无解，输出一行 $-1$。否则，输出一行 $n$ 个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为 $1 \\sim m$。"},{"iden":"note","content":"**【样例解释】**\n\n在第一组数据中，一个合法的完美匹配是 $(1, 6),(2, 5),(3, 4)$，且里面有恰好两条黑色边。\n\n在第二组数据中，虽然存在完美匹配，但每个完美匹配都有奇数条黑色边。\n\n**【数据范围】**\n\n**本题使用子任务捆绑测试。**\n\n对于所有数据，保证 $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)$。\n\n- Subtask 1（20%）：$n ≤ 8$，$T ≤ 10$。\n- Subtask 2（20%）：$n ≤ 18$，$T ≤ 10$。\n- Subtask 3（20%）：$c_i$ 在 $\\{0, 1\\}$ 里独立均匀随机。\n- Subtask 4（40%）：无特殊限制。"}],"translated_statement":null,"sample_group":[["2\n3 7\n3 6 1\n2 6 0\n2 5 1\n3 5 1\n1 6 1\n3 4 0\n1 5 1\n3 7\n1 6 1\n3 5 1\n2 5 1\n3 4 1\n1 5 0\n1 4 0\n2 6 0","5 3 6\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}