4732: 匹配(广东省重点中学信息学邀请赛提高组)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
广东省重点中学信息学邀请赛(GDKOI 2024 day1提高组第一试)
给定一个2n个点m条边的二分图，左部点编号为1∼n，右部点编号为n+1∼2n。
给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。
如果你对二分图的定义有疑问：
•二分图是一个无向图，点分为左右两部分，每部分各n个点，每条边都连接两个属于不同部分的点。
•一个完美匹配是一个大小为n的边的集合，使得每个点都恰好与集合里的一条边相连。
给定一个2n个点m条边的二分图，左部点编号为1∼n，右部点编号为n+1∼2n。
给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。
如果你对二分图的定义有疑问：
•二分图是一个无向图，点分为左右两部分，每部分各n个点，每条边都连接两个属于不同部分的点。
•一个完美匹配是一个大小为n的边的集合，使得每个点都恰好与集合里的一条边相连。
输入
第一行一个正整数T，表示数据组数。每组数据的格式如下：
第一行两个正整数n,m，表示图的点数和边数。接下来m行，每行三个整数ui,vi,ci(1≤ui≤n,n+1≤vi≤2n,0≤ci≤1)，表示一条连接ui,vi的边，颜色为ci。ci=0表示白色，ci=1表示黑色。
第一行两个正整数n,m，表示图的点数和边数。接下来m行，每行三个整数ui,vi,ci(1≤ui≤n,n+1≤vi≤2n,0≤ci≤1)，表示一条连接ui,vi的边，颜色为ci。ci=0表示白色，ci=1表示黑色。
输出
对于每组数据：如果无解，输出一行‘-1‘。否则，输出一行n个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为1∼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,6),(2,5),(3,4) ，且里面有恰好两条黑色边。