信息学奥赛题库- 星空穿越

友情提示：380元/半年，儿童学编程，就上码丁实验室。

【题目描述】

$A$国所在的星系共有$n$个星球,星球间有$m$条双向通道。$A$国星球间的传送不仅耗时而且代价高昂。为了防止偷渡者的出现，$A$国有一种特殊的手段可以检查每条通道是被通过了奇数次还是偶数次。

由于调兵，这$m$条通道中的一些通道已经被经过了奇数次。现在你的任务是：安排尽量少的人，每个人在星球间沿一条路径传送(不一定是简单路径)，使得每条通道都被经过偶数次。

【输入】

输入包含多组数据，其中输入的第一行是数据组数$T$。

第一行$2$个正整数$n,m$，表示城市数和剩余的通道数目。

接下来$m$行每行$3$个正整数$a,b,c$，表示有一条城市$a$和$b$之间的双向通道。当$c=1$时说明经过了奇数次，$0$表示经过了偶数次。

保证$a≠b$，且不存在$i,j$，满足$max(a_i,b_i)=max(a_j,b_j)$且$min(a_i,b_i)=min(a_j,b_j)$。

【输出】

第一行一个整数$K$，表示你安排的人数。

接下来$K$行，每行的第一个数为一个正整数$l$，表示第$i$个人走过的路径中的节点数。接下来$l$个数表示第$i$个人走过的路径是$v_1,v_2,…,v_l$。

若对于一个测试点中的每组数据，你的程序第一行的答案都是正确的，且每组数据的输出都是满足格式要求的，那么设这个子任务的总分为$x$，你可以得到$0.35x$的分数。注意为了得到这一部分的分数你没有必要输出正确的解，而是只要输出任意K条合法的路径即可。但你必须要保证对于一个测试点来说你输出的路径的$l$之和不能超过$5×10^6$且$l>0$。

【输入样例】

1
13 14
1 2 1
2 3 1
3 4 1
2 4 1
1 4 0
4 6 1
4 10 0
2 5 1
2 7 0
7 8 1
8 9 1
9 7 1
11 12 1
11 13 1

【输出样例】

3
5 1 2 3 4 6
8 4 2 7 8 9 7 2 5
3 12 11 13

【提示】

【数据规模及约定】

对于100%的数据，保证$0 ≤ c_i ≤ 1,sum n ≤ 5 × 10^5,sum m ≤ 5 × 10^5$。