{"problem":{"name":"[GDKOI2024 提高组] 匹配","description":{"content":"给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \\sim n$，右部点编号为 $n + 1 \\sim 2n$。 给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。 如果你对二分图的定义有疑问： - 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。 - 一个完美匹配是一个大小为 $n$ 的边的集合","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10080"},"statements":[{"statement_type":"Markdown","content":"给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \\sim n$，右部点编号为 $n + 1 \\sim 2n$。\n\n给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。\n\n如果你对二分图的定义有疑问：\n\n- 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。\n- 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。\n\n## Input\n\n第一行一个正整数 $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$ 表示黑色。\n\n## Output\n\n对于每组数据：如果无解，输出一行 $-1$。否则，输出一行 $n$ 个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为 $1 \\sim m$。\n\n[samples]\n\n## Note\n\n**【样例解释】**\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%）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10080","tags":["2024","广东","Special Judge","O2优化","广度优先搜索 BFS","深度优先搜索 DFS","二分图"],"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"]],"created_at":"2026-03-03 11:09:25"}}