[HOJ] 99 - 垃圾處理

#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#define N 100005
using namespace std;
struct P{
    int v,c;
};
vector<P> edge;
vector<int> sta,s[N],ans,tmp;
vector<vector<int> > out;
int in[N]{0},vi[N]={0},pp[N]={0},aa[N]={0};
void dfs(int u){
    int i,k;
    vi[u]=1;
    for(;aa[u]<s[u].size();aa[u]++){
        i=aa[u];
        int v=s[u][i];
        if(edge[v].c){
            edge[v].c=edge[v^1].c=0;
            dfs(edge[v].v);
            sta.push_back(edge[v].v);
        }
    }
}
int main(){
    //freopen("smi3a.in","r",stdin);
    int i,j,n,m,x,y,a,b,add=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d%d",&x,&y,&a,&b);
        if(a^b){
            s[x].push_back(edge.size());
            s[y].push_back(edge.size()+1);
            in[x]++;
            in[y]++;
            edge.push_back((P){y,1});
            edge.push_back((P){x,1});
        }
    }
    for(i=1;i<=n;i++){
        if(in[i]%2){
            puts("NIE");
            return 0;
        }
    }
    for(i=1;i<=n;i++){
        if(vi[i]==0){
            sta.clear();
            vi[i]=1;
            dfs(i);
            sta.push_back(i);
            for(j=0;j<sta.size();j++){
                //printf("%d ",sta[j]);
                if(pp[sta[j]]){
                    add++;
                    ans.clear();
                    ans.push_back(sta[j]);
                    while(tmp.back()!=sta[j]){
                        ans.push_back(tmp.back());
                        pp[tmp.back()]=0;
                        tmp.pop_back();
                    }
                    pp[tmp.back()]=0;
                    ans.push_back(tmp.back());
                    tmp.pop_back();
                    out.push_back(ans);
                    /*for(x=0;x<ans.size();x++){
                        printf("%d ",ans[x]);
                    }puts("");*/
                }
                tmp.push_back(sta[j]);
                pp[sta[j]]=1;
            }//puts("");
        }
    }
    printf("%d\n",add);
    for(i=0;i<out.size();i++){
        ans=out[i];
        printf("%d",ans.size()-1);
        for(j=0;j<ans.size();j++){
            printf(" %d",ans[j]);
        }
        puts("");
    }
}