显然，对于初始颜色与目标颜色不同的边，我们需要走过奇数次；对于初始颜色与目标颜色相同的边，我们需要走过偶数次。
对于只有偶数边的情况，这种情况下不走就行；对于只有奇数边；可以理解为每条边只能经过一次，就是欧拉路径问题，并且考虑这题的特殊性质，如果一个图是由若干个简单环构成的连通图，那么显然每个点度数为偶数，毕竟环都是进一次出一次。所以在判断方面，只需判断偶数边即可。
那么我们考虑将两种情况合起来，可以发现，如果只有奇数边情况无解，那么加几个偶数边也无济于事，所以对于偶数边，就不用加了，只加奇数边，那么一定会形成若干连通块，分别对每个连通块进行考虑即可。
对于一个连通块，先求出其欧拉路径，然后用类似 tarjan 的方法，设置一个栈，一旦遇到与当前栈的元素重复就加进新的答案。具体看代码。
有一说一，原来用的 \(vector+map\) 做，超时，但是用邻接表做则可以AC，果然常数还是太大了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define PII pair<int,int>
inline LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=1e5+10,M=2e6+10;
int n,m,ans_cnt;
int fa[N],vis[N];
int del[N],deg[N];
vector<int> id[N],ans[N];
stack<int> st;
int f[M],tot=1,h[N],to[M],nxt[M];
void add(int x,int y) {
to[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
}
int find(int x) {
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void merge(int x,int y) {
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fx]=fy;
}
void dfs(int nd) {
for(int i=h[nd];i;i=nxt[i]) {
if(f[i]) continue;
int x=to[i];
f[i]=f[i^1]=1;
h[nd]=nxt[i];
dfs(x);
}
st.push(nd);
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) {
int a=read(),b=read(),s=read(),t=read();
if(s!=t) {
add(a,b); add(b,a);
deg[a]++; deg[b]++;
merge(a,b);
}
}
for(int i=1;i<=n;i++) {
id[find(i)].push_back(i);
}
for(int i=1;i<=n;i++) {
if(fa[i]==i) {
int cnt=0,sz=id[i].size();
for(int x:id[i]) {
if(deg[x]%2==0) cnt++;
}
if(cnt==sz) {
dfs(id[i][0]);
stack<int> stk;
while(st.size()) {
int x=st.top(); st.pop();
if(vis[x]) {
++ans_cnt; int y=0;
do {
y=stk.top();
ans[ans_cnt].push_back(y);
vis[y]=0; stk.pop();
}while(y!=x);
}
stk.push(x); vis[x]=1;
}
}
else {
cout<<"NIE"; return 0;
}
}
}
cout<<ans_cnt<<endl;
for(int i=1;i<=ans_cnt;i++) {
cout<<ans[i].size()<<" ";
for(int x:ans[i]) cout<<x<<" ";
cout<<ans[i][0]<<"\n";
}
return 0;
}