#include <bits/stdc++.h>
using namespace std;
int removed[4], ok[4], n, cycles, phase, ans;
struct graph
{
vector<int> adj[1000005];
int par[1000005];
graph()
{
for (int i=1; i<=n; i++)
par[i]=i;
}
} *original;
struct graph2
{
int par[1000005];
short int deg[1000005];
graph2()
{
for (int i=1; i<=n; i++)
par[i]=i, deg[i]=0;
}
} *newgraphs[4];
int findPar(int u, graph *g)
{
return g->par[u]==u?u:(g->par[u]=findPar(g->par[u], g));
}
int findPar(int u, graph2 *g)
{
return g->par[u]==u?u:(g->par[u]=findPar(g->par[u], g));
}
void addEdge(int u, int v, graph *g)
{
g->adj[u].push_back(v);
g->adj[v].push_back(u);
g->par[findPar(u, g)]=findPar(v, g);
}
void addEdge(int u, int v, graph2 *g)
{
g->deg[u]++;
g->deg[v]++;
g->par[findPar(u, g)]=findPar(v, g);
}
int checkEdge(int u, int v, graph2 *g)
{
if (g->deg[u]==2 || g->deg[v]==2)
return 0;
int pu=findPar(u, g), pv=findPar(v, g);
if (pu==pv)
return 0;
addEdge(u, v, g);
return 1;
}
void startPhase(int u)
{
phase=1;
removed[0]=u;
removed[1]=original->adj[u][0];
removed[2]=original->adj[u][1];
removed[3]=original->adj[u][2];
for (int i=0; i<4; i++)
{
newgraphs[i]=new graph2;
ok[i]=1;
for (int j=1; j<=n; j++)
{
if (j==removed[i])
continue;
for (int u:original->adj[j])
{
if (u!=removed[i] && j<u)
{
if (!checkEdge(j, u, newgraphs[i]))
{
ok[i]=0;
delete newgraphs[i];
break;
}
}
}
if (!ok[i])
break;
}
}
delete original;
}
void Init(int N)
{
ans=n=N;
original=new graph;
}
void Link(int u, int v)
{
u++, v++;
if (!ans)
return;
if (phase)
{
for (int i=0; i<4; i++)
{
if (u!=removed[i] && v!=removed[i] && ok[i] && !checkEdge(u, v, newgraphs[i]))
{
ok[i]=0;
delete newgraphs[i];
}
}
return;
}
if (original->adj[u].size()==2)
{
addEdge(u, v, original);
startPhase(u);
return;
}
if (original->adj[v].size()==2)
{
addEdge(u, v, original);
startPhase(v);
return;
}
int pu=findPar(u, original), pv=findPar(v, original);
if (pu==pv)
{
if (cycles)
{
ans=0;
return;
}
cycles=1;
int cur=u, pre;
ans=1;
while (cur!=v)
{
ans++;
if (original->adj[cur].size()==1)
{
pre=cur;
cur=original->adj[cur][0];
}
else
{
int node1=original->adj[cur][0];
int node2=original->adj[cur][1];
if (node1==pre)
{
pre=cur;
cur=node2;
}
else
{
pre=cur;
cur=node1;
}
}
}
}
addEdge(u, v, original);
}
int CountCritical()
{
if (phase)
return ok[0]+ok[1]+ok[2]+ok[3];
return ans;
}
