jisoo

可以证明，一定只需要考虑需要翻转的边

如果一种合法方案，需要翻转不需要翻转的边，那么就必然有一个过程是把这条边翻转过来，

那么这一条边有两种可能，要不它连着偶数个由需要翻转的边组成的环，要不是有许多同样的此类不翻转边组成的环

对于以上两种可能，可以发现都会出现需要翻转的边连成环的可能。

然后如此,就是求欧拉回路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
int n,m;
int x,y,z,k;
int du[2000005];
stack<int> s;
struct ed{
    int to;
    int ne;
}ed[2000001];
int be[2000001];
int use[2000001];
int cnt;
int vis[2000001];
int c;
int p=1;
int head[2000001];
void add(int f,int to){
    p++;
    ed[p].ne=head[f];
    ed[p].to=to;
    head[f]=p;
}
void dfs(int no,int r){
//  cout<<no<<endl;
    s.push(no);
    du[no]-=2;
    for(int i=head[no];i;i=ed[i].ne){
        head[no]=i;
        if(use[i]) continue;
        use[i]=use[i^1]=1;
        if(no!=r&&ed[i].to==r){
            s.push(r);
            cnt++;
            return ;
        }
        dfs(ed[i].to,r);
        return ;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&x,&y,&z,&k);
        if(z+k==1){
            add(x,y);
            add(y,x);
            du[x]++;
            du[y]++; 
        } 
    }
    for(int i=1;i<=n;++i){
        if(du[i]&1){
            cout<<"NIE";
            return 0;
        }
    }
    for(int i=1;i<=n;++i){
        if(!du[i]) continue;
        while(du[i]){
            //cout<<" sf"<<du[i]<<endl;
            dfs(i,i);
        }
    }
    cout<<cnt<<endl;
//  while(!s.empty()){
//      cout<<s.top()<<endl;
//      s.pop();
//  }
    while(!s.empty()){
        int aim=s.top();
        s.pop();
        int cnt=0;
        vis[cnt]=aim;
        while(s.top()!=aim){
            vis[++cnt]=s.top();
            s.pop();
        }
        printf("%d ",cnt+1);
        s.pop();
        for(int i=0;i<=cnt;++i){
            printf("%d ",vis[i]);
        }
        printf("%dn",vis[0]);
    }
    return 0;
}