【题目描述】
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(ai,bi)=max(aj,bj)且min(ai,bi)=min(aj,bj)。
【输出】
第一行一个整数K，表示你安排的人数。
接下来K行，每行的第一个数为一个正整数l，表示第i个人走过的路径中的节点数。接下来l个数表示第i个人走过的路径是v1,v2,…,vl。
若对于一个测试点中的每组数据，你的程序第一行的答案都是正确的，且每组数据的输出都是满足格式要求的，那么设这个子任务的总分为x，你可以得到0.35x的分数。注意为了得到这一部分的分数你没有必要输出正确的解，而是只要输出任意K条合法的路径即可。但你必须要保证对于一个测试点来说你输出的路径的l之和不能超过5×106且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≤ci≤1,∑n≤5×105,∑m≤5×105。
测试点编号 测试点分值 n m T 约定
1 17 ≤10 ≤10 =20 无
2 22 ≤300 ≤3000 =15 无
3 24 ≤2×10^5 2×10^5 =10 ci=1
4 37 ≤2×10^5 2×10^5 =10 无
去除所有的偶数次双向通路，剩下的奇数边构成的图看节点的度数，(奇数度的节点的个数/2)是所需的人的个数
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set::iterator sit;
namespace INPUT_SPACE{
const int BS=(1<<27)+5;char Buffer[BS],*HD,*TL;
char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
inline int inn()
{
int x,ch;while((ch=gc())<'0'||ch>'9');
x=ch^'0';while((ch=gc())>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^'0');return x;
}
}using INPUT_SPACE::inn;
namespace OUTPUT_SPACE{
char ss[36000000],tt[10];int ssl,ttl;
inline int PC(char c) { return ss[++ssl]=c; }
inline int print(int x)
{
if(!x) ss[++ssl]='0';
for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+'0');
for(;ttl;ttl--) ss[++ssl]=tt[ttl];return 0;
}
inline int Flush() { return fwrite(ss+1,sizeof(char),ssl,stdout),0; }
}using OUTPUT_SPACE::print;using OUTPUT_SPACE::PC;using OUTPUT_SPACE::Flush;
const int N=200002,M=500002;
struct edges{
int to,pre,w;
}e[M<<1];int h[N],etop,vis[N],d[N],del[M<<1],allz,top,s[M];
inline int add_edge(int u,int v,int w) { return e[++etop].to=v,e[etop].pre=h[u],e[etop].w=w,del[etop]=0,h[u]=etop; }
inline int build_edge(int u,int v,int w) { return add_edge(u,v,w),add_edge(v,u,w); }
#define ot(i) ((((i)-1)^1)+1)
#define clr(a,n) memset(a,0,sizeof(int)*((n)+1))
int dfs(int x)
{
vis[x]=1;
for(int &i=h[x],j;i;i=e[i].pre)
{
if(del[i]) continue;allz&=(e[i].w==0),j=i,
del[i]=del[ot(i)]=1,dfs(e[i].to),s[++top]=j;
}
return 0;
}
vector ans[M];
int main()
{
for(int T=inn();T;T--)
{
int n=inn(),m=inn(),cnt=0;
clr(h,n),clr(d,n),clr(vis,n),etop=0;
rep(i,1,m)
{
int x=inn(),y=inn(),z=inn();
build_edge(x,y,z);
if(!z) build_edge(x,y,z);
else d[x]^=1,d[y]^=1;
}
for(int i=1,las=0;i<=n;i++) if(d[i])
{ if(las) build_edge(i,las,-1),las=0;else las=i; }
rep(i,1,n) if(!vis[i])
{
allz=1,top=0,dfs(i);if(allz) continue;int t=cnt+1;
ans[++cnt].clear(),ans[cnt].pb(e[ot(s[top])].to);
for(int j=top;j;j--)
{
if(e[s[j]].w==-1) ans[++cnt].clear();
ans[cnt].pb(e[s[j]].to);
}
if(t<cnt)
{
ans[cnt].pop_back();
Rep(j,ans[t]) ans[cnt].push_back(ans[t][j]);
ans[t].clear(),swap(ans[t],ans[cnt]),cnt--;
}
}
print(cnt),PC('\n');
rep(i,1,cnt)
{
print((int)ans[i].size());
Rep(j,ans[i]) PC(' '),print(ans[i][j]);
PC('\n');
}
}
return Flush(),0;
}