#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
bool was_cycle;
set<int> ok;
vector<int> e[N+10];
int fau[N+10];
bool on_cycle[N+10];
bool vis[N+10];
bool vis2[N+10];
int pp[N+10];
int f(int x)
{
if(fau[x]!=x)
fau[x]=f(fau[x]);
return fau[x];
}
void u(int x,int y)
{
fau[f(y)]=f(x);
return;
}
void set_all(bool c)
{
ok.clear();
if(c)
{
for(int i=0;i<n;i++)
ok.insert(i);
}
return;
}
bool dfs(int x,int y)
{
if(x==y)
{
on_cycle[x]=true;
return true;
}
vis[x]=true;
for(auto v:e[x])
{
if(!vis[v] && dfs(v,y))
{
on_cycle[x]=true;
return true;
}
}
return false;
}
void dfs2(int x,int id)
{
vis2[x]=true;
pp[x]=id;
for(auto v:e[x])
{
if(vis2[v] || on_cycle[v])
continue;
dfs2(v,id);
}
return;
}
void check_deg(int x)
{
if(ok.empty())
return;
if(e[x].size()>3)
{
if(ok.find(x)!=ok.end())
{
ok.clear();
ok.insert(x);
}
else
ok.clear();
}
else if(e[x].size()==3)
{
vector<int> trash;
set<int> ee={x,e[x][0],e[x][1],e[x][2]};
for(auto v:ok)
{
if(ee.find(v)==ee.end())
trash.push_back(v);
}
for(auto v:trash)
ok.erase(v);
}
return;
}
bool are_ngh(int x,int y)
{
for(auto v:e[x])
{
if(v==y)
return true;
}
return false;
}
void Init(int _N)
{
n=_N;
set_all(true);
for(int i=0;i<n;i++)
fau[i]=i;
was_cycle=false;
return;
}
void Link(int A,int B)
{
if(ok.empty())
return;
if(f(A)==f(B))
{
if(was_cycle)
{
if(on_cycle[A] && on_cycle[B])
{
set<int> st;
for(int v:{A,B})
{
if(ok.find(v)!=ok.end())
st.insert(v);
}
ok=st;
}
else if(vis2[A] && vis2[B])
{
if(pp[A]==pp[B])
{
if(ok.find(pp[A])!=ok.end())
{
ok.clear();
ok.insert(pp[A]);
}
else
ok.clear();
}
else if(are_ngh(pp[A],pp[B]))
{
set<int> st;
for(int v:{pp[A],pp[B]})
{
if(ok.find(v)!=ok.end())
st.insert(v);
}
ok=st;
}
else
ok.clear();
}
else
ok.clear();
}
else
{
was_cycle=true;
dfs(A,B);
for(int i=0;i<n;i++)
{
if(ok.find(i)!=ok.end() && !on_cycle[i])
ok.erase(i);
}
for(int i=0;i<n;i++)
{
if(on_cycle[i])
dfs2(i,i);
}
}
}
u(A,B);
e[A].push_back(B);
e[B].push_back(A);
if(vis2[A] && !vis2[B])
dfs2(B,pp[A]);
if(vis2[B] && !vis2[A])
dfs2(A,pp[B]);
check_deg(A);
check_deg(B);
return;
}
int CountCritical()
{
return ok.size();
}
