#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int ans , n , deg[N];
bool flg;
vector <int> adj[N];
struct Graph{
int vert , par[N] , d[N];
bool ok , marked[N];
vector <int> all[N];
void Dfs(int v , int p = -1)
{
marked[v] = true;
par[v] = (p == -1 ? v : par[p]);
int D = (p != -1);
for(auto u : adj[v]) if(u != vert)
{
if(!marked[u])
{
D++;
Dfs(u , v);
}
else if(u != p)
ok = false;
}
if(D > 2)
ok = false;
d[v] = D;
}
int root(int v)
{
return (par[v] == v ? v : par[v] = root(par[v]));
}
void Build()
{
ok = true;
marked[vert] = true;
for(int i = 0 ; i < n ; i++) if(!marked[i])
Dfs(i);
}
void Add(int a , int b)
{
if(a == vert || b == vert)
return;
int ra = root(a) , rb = root(b);
if(d[a] > 1 || d[b] > 1 || ra == rb)
{
ok = false;
return;
}
par[rb] = ra;
d[a]++;
d[b]++;
}
} graph[5];
struct DSU{
int sz[N] , par[N];
void Build()
{
for(int i = 0 ; i < n ; i++)
{
par[i] = i;
sz[i] = 1;
}
}
int root(int v)
{
return (par[v] == v ? v : par[v] = root(par[v]));
}
void Merge(int a , int b)
{
deg[a]++; deg[b]++;
adj[a].push_back(b);
adj[b].push_back(a);
if(deg[a] < deg[b])
swap(a , b);
int ra = root(a) , rb = root(b);
//cout << a << " --- " << b << " " << ra << " " << rb << endl;
if(deg[a] == 3)
{
graph[0].vert = a;
for(int i = 1 ; i <= 3 ; i++)
graph[i].vert = adj[a][i - 1];
for(int i = 0 ; i < 4 ; i++)
graph[i].Build();
flg = true;
return;
}
if(ra == rb)
{
ans = (ans == n ? sz[ra] : 0);
return;
}
par[rb] = ra;
sz[ra] += sz[rb];
}
} dsu;
void Init(int x)
{
n = x;
ans = x;
dsu.Build();
}
void Link(int a , int b)
{
if(!flg)
dsu.Merge(a , b);
else
{
for(int i = 0 ; i < 4 ; i++)
graph[i].Add(a , b);
}
}
int CountCritical()
{
if(!flg)
return ans;
else
{
int cnt = 0;
for(int i = 0 ; i < 4 ; i++)
cnt += graph[i].ok;
return cnt;
}
}
