cf860d wizard’s tour

#include <bits/stdc++.h>
using namespace std;
const int maxn=2*100000+5;
inline int ()
{
    char c;int tmp=0,x=1;c=getchar();
    while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
    while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
    return tmp*x;
}
int tot=0,extr=0,head[2][maxn*5],ed[2][maxn*5],nxt[2][maxn*5],n,m,sons[maxn*5];
void addedge(int id,int from,int to)
{
    assert(to!=0);assert(from!=0);
    ed[id][tot]=to;nxt[id][tot]=head[id][from];head[id][from]=tot;tot++;
    ed[id][tot]=from;nxt[id][tot]=head[id][to];head[id][to]=tot;tot++;
}
bool vis[maxn*5],edvis[maxn*5],lev[maxn*5];
int cnt[maxn*5];
struct trio{int u,v,w;
    trio(int u=0,int v=0,int w=0): u(u),v(v),w(w) {}
};
vector<trio > Ege;
#define MP make_pair
map<int ,int > rfl;
void dfs(int v)
{
    vis[v]=true;
    for(int i=head[0][v];i!=-1;i=nxt[0][i]){
        if(edvis[i]) continue;
        edvis[i]=edvis[i^1]=true;
        int u=ed[0][i];
        if(vis[u]) addedge(1,v,++extr),rfl[extr]=u;
        else {addedge(1,v,u);dfs(u);}
        sons[v]++;
    }
}
vector<pair<int ,int> > aoi[maxn*5];
vector<int > shiroi[maxn*5];
void Perform(int v)
{
    vis[v]=true;
    int rest=0;
    aoi[v].clear();shiroi[v].clear();
    for(int i=head[1][v];i!=-1;i=nxt[1][i]){
        int u=ed[1][i];
        if(!vis[u]) {
            Perform(u);
            rest+=lev[u];
            cnt[v]+=cnt[u];
            if(lev[u]) {
                aoi[v].push_back(MP(u,shiroi[u].back()));
                shiroi[u].pop_back();
                assert(shiroi[u].empty());
            }else shiroi[v].push_back(u);
        }
    }
    int left=sons[v]-rest,U,V;
    for(int i=1;i<=rest;i++){
        Ege.push_back(trio(v,aoi[v][i-1].first,aoi[v][i-1].second));
    }
    for(int i=1;i<=left/2;i++){
        U=shiroi[v].back(),shiroi[v].pop_back();
        V=shiroi[v].back(),shiroi[v].pop_back();
        Ege.push_back(trio(U,v,V));
    }
    assert((int)shiroi[v].size()<=1);
    cnt[v]+=left/2+rest;lev[v]=(left&1);
}
int Change(int v){if(v>n) return rfl[v];else return v;}
int main()
{
    n=readint(),m=readint();
    extr=n;
    int u,v;
    memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt));
    for(int i=1;i<=m;++i)
        u=readint(),v=readint(),addedge(0,u,v);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
    memset(vis,0,sizeof(vis[0])*(extr+1));
    int ans=0;
    for(int i=1;i<=extr;i++)
        if(!vis[i]) {Perform(i);ans+=cnt[i];}
    printf("%dn",ans);
    for(int i=0;i<(int)Ege.size();i++){
        Ege[i].v=Change(Ege[i].v),Ege[i].u=Change(Ege[i].u),Ege[i].w=Change(Ege[i].w);
    }
    for(int i=0;i<(int)Ege.size();i++) printf("%d %d %dn",Ege[i].u,Ege[i].v,Ege[i].w);
    return 0;
}