Description：

给定 $n$ 个点 $m$ 条边，每条边有一个初始权值 $0$ 或 $1$ ，有一个最终权值 $0$ 或 $1$ ，每次可以给一个简单环上的边权值异或 $1$ ，求一种方案使得每条边从初始权值变成最终权值，无解输出 $NIE$ 。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 10^6$

Solution：

只考虑需要反转的边，把其他边都删掉，无解就是有一个点度数为奇数，构造答案的过程就是每次要从 $i$ 走到 $j$ 时，就把 $i$ 压进去，如果进入了一个已经在栈内的点，就不停弹栈直到弹到了那个点位置，弹出的就构成了一个简单环。正确性没问题，但不是很懂为什么要这样做。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXM 1000010

struct edge

{

	int to,nxt;

	int tag;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN] = {0};

void add(int a,int b)

{

	++ind[a];++ind[b];

	e[edgenum] = (edge){b,lin[a],1};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],1};lin[b] = edgenum++;

	return;

}

bool ins[MAXN];

int stack[MAXN],top = 0;

int ans = 0;

vector<int> res[MAXM * 3];

bool v[MAXN];

void dfs(int k)

{

	v[k] = true;

	if(ins[k])

	{

		int t = 0;

		++ans;

		res[ans].push_back(k);

		while(t != k)

		{

			t = stack[top];

			res[ans].push_back(stack[top]);

			ins[stack[top]] = false;

			--top;

		}

	}

	for(int &i = lin[k];i != -1;i = e[i].nxt)

	{

		if(e[i].tag)

		{

			e[i].tag = e[i ^ 1].tag = 0;

			stack[++top] = k;

			ins[k] = true;

			dfs(e[i].to);

		}

	}

	return;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	int a,b,c,d;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&a,&b,&c,&d);

		if(c ^ d)add(a,b);

	}

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] % 2 == 1)

		{

			puts("NIE");

			return 0;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		if(!v[i])dfs(i);

	}

	cout << ans << endl;

	for(int i = 1;i <= ans;++i)

	{

		printf("%d ",res[i].size() - 1);

		for(vector<int>::iterator it = res[i].begin();it != res[i].end();++it)

		{

			printf("%d ",*it);

		}

		puts("");

	}

	return 0;

}