p3520

记录

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdlib>
#include<iomanip>
#include<map>
#define int long long
#define double long double
#define lc(p) p<<1
#define rc(p) p<<1|1
#define pii pair<int,int>
using namespace std;
struct edge{
    int v;
    int rev;
    bool exs;
};

int d[100007];
int del[100007];
bool vis[100007];
int reftop[100007];
vector<edge> e[100007];
stack<int> ans[100007];
map<int,bool> mp;
int tpp=0;
bool f=false;
void dfs(int now){
    if(f)return;
    if(mp[now]==true){
        f=true;
        return;
    }
    vis[now]=true;
    mp[now]=true;
    for(int &i=del[now];i<e[now].size();){
        if(e[now][i].exs){
            edge t=e[now][i];
            e[now][i].exs=0;
            e[t.v][t.rev].exs=0;
            i++;
            dfs(t.v);
        }
        else i++;
    }
    ans[tpp].push(now);
}
int n,m;
signed main(){ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,b1,b2;
        cin>>u>>v>>b1>>b2;
        if(b1!=b2){
            e[u].push_back({v,0,1});
            e[v].push_back({u,0,1});
            d[u]++;
            d[v]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();i++){
            e[i][j].rev=reftop[e[i][j].v]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(d[i]&1){
            cout<<"NIE"<<endl;
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            tpp++;
            dfs(i);
            mp.clear();
            f=false;
        }
    }
    cout<<tpp<<endl;
    for(int i=1;i<=tpp;i++){
        cout<<ans[i].size()<<" ";
        int fir=ans[i].top();
        while(!ans[i].empty()){
            cout<<ans[i].top()<<" ";
            ans[i].pop();
        }
        cout<<fir<<endl;
    }
}
//然后我测了一下n=20，飞快啊！
//n=30，同样飞快！
//n=40，还是能跑！
//然后一一测过去，测到n=100，也跑过去了！
//太震撼了！
//selfeval，启动！
//0.05s!100分！
//是不是ak了！一看时间，4h！