#include<bits/stdc++.h>
using namespace std;
int N;
set<int>s[2000005];
int cur=0;
int p[1000005];
int in[1000005];
int fp(int a){return p[a]==a?a:p[a]=fp(p[a]);}
void un(int a,int b){p[fp(b)]=fp(a);}
vector<int>adj[1000005];
void Init(int N_) {
N = N_;
for(int i=0;i<N;i++)s[0].insert(i),p[i]=i;
}
void add(vector<int>v){
cur++;
for(auto x:v){
if(s[cur-1].count(x))s[cur-1].erase(x),s[cur].insert(x);
}
//cerr<<s[cur].size()<<":\n";
//for(auto x:s[cur])cerr<<x<<" ";
//cerr<<"\n";
}
void add_3(int u){
vector<int>temp;
temp.push_back(u);
for(auto x:adj[u]){
temp.push_back(x);
}
add(temp);
}
int vis[1000005];
int tvis[1000005];
int cycle=0;
int from[1000005];
void dfs(int u,int p=-1){
if(tvis[u])return;
//cerr<<"dfs:"<<u<<" "<<p<<"\n";
from[u]=p;
tvis[u]=1;
for(auto x:adj[u])if(x!=p)dfs(x,u);
}
void Link(int A, int B) {
if(s[cur].size()==0)return;
in[A]++;
in[B]++;
adj[A].push_back(B);
adj[B].push_back(A);
if(vis[A])from[B]=A;
if(vis[B])from[A]=B;
if(fp(A)==fp(B)){
if(cycle){
if(vis[A]&&vis[B])return add({A,B});
if(!vis[A]&&!vis[B])return void(cur++);
if(vis[A])swap(A,B);
int temp=A;
while(!vis[temp]){
vis[temp]=1;
temp=from[temp];
}
add({A,B});
}else{
cycle=1;
dfs(A,B);
int temp=B;
vector<int>loop;
while(temp!=A)/*cerr<<"re loop:"<<temp<<"\n",*/loop.push_back(temp),vis[temp]++,temp=from[temp];
loop.push_back(A);
vis[A]++;
//cerr<<"in loop:\n";
//for(auto x:loop)cerr<<x<<" ";
//cerr<<"\n";
add(loop);
}
}
un(A,B);
if(in[A]==3)add_3(A);
if(in[B]==3)add_3(B);
if(in[A]>3)add({A});
if(in[B]>3)add({B});
}
int CountCritical() {
return s[cur].size();
}
