#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int N,mode;
vector<int> p[5];
mat path[5];
void init(int n,int k){
p[k].resize(n);
path[k].assign(n,vec());
for(int i=0;i<n;i++)p[k][i]=i;
}
int find(int x,int k){
if(p[k][x]==x)return x;
return p[k][x]=find(p[k][x],k);
}
bool merge(int x,int y,int k){
x=find(x,k),y=find(y,k);
if(x==y)return 0;
p[k][x]=y;
return 1;
}
void finish(int k){
p[k].clear();
path[k].clear();
}
bool CircleChk[1000000],chk[4];
int cnt,Ex[4];
void Init(int n){
N=n;
init(n,4);
}
int CountCritical(){
// Base
if(mode==0){
return N;
}
// Circle
else if(mode==1){
return cnt;
}
// Divided
else if(mode==2){
cnt=0;
for(int k=0;k<4;k++)if(!chk[k])cnt++;
if(cnt==0)mode=-1;
return cnt;
}
// End
else{
return 0;
}
}
void CircleBfs(int v){
queue<int> Q;
Q.push(v);
CircleChk[v]=1;
while(!Q.empty()){
v=Q.front();
cnt++;
Q.pop();
for(int i=0;i<path[4][v].size();i++){
int u=path[4][v][i];
if(!CircleChk[u]){
Q.push(u);
CircleChk[u]=1;
}
}
}
}
void make_graph(int x,int k){
init(N,k);
Ex[k]=x;
for(int i=0;i<N;i++){
if(x==i)continue;
for(int t=0;t<path[4][i].size();t++){
int j=path[4][i][t];
if(j==x)continue;
path[k][i].pb(j);
merge(i,j,k);
}
if(path[k][i].size()>2){
chk[k]=1;
return;
}
}
}
void Link(int x,int y){
//End
if(mode<0)return;
// Base
if(mode==0){
path[4][x].pb(y);
path[4][y].pb(x);
if(path[4][x].size()<path[4][y].size())swap(x,y);
if(path[4][x].size()>2){
mode=2;
for(int i=0;i<3;i++)
make_graph(path[4][x][i],i);
make_graph(x,3);
finish(4);
return;
}
if(!merge(x,y,4)){
cnt=0;
mode=1;
CircleBfs(x);
}
}
// Circle
else if(mode==1){
path[4][x].pb(y);
path[4][y].pb(x);
if(!merge(x,y,4)){
mode=-1;
return;
}
if(path[4][x].size()<path[4][y].size())swap(x,y);
if(path[4][x].size()>2){
if(CircleChk[x]==0&&CircleChk[y]==0){
mode=-1;
return;
}
mode=2;
for(int i=0;i<path[4][x].size();i++){
if(!CircleChk[path[4][x][i]]){
chk[i]=1;
continue;
}
make_graph(path[4][x][i],i);
}
make_graph(x,3);
finish(4);
return;
}
}
// Divided
else if(mode==2){
for(int k=0;k<4;k++){
if(chk[k])continue;
if(Ex[k]==x||Ex[k]==y)continue;
path[k][x].pb(y);
path[k][y].pb(x);
if(!merge(x,y,k))chk[k]=1;
if(path[k][x].size()<path[k][y].size())swap(x,y);
if(path[k][x].size()>2){
chk[k]=1;
}
}
}
}
