#include <bits/stdc++.h>
using namespace std;
struct UF{
int t[1000000];
void init(){
for(int i=0;i<1000000;i++){
t[i]=-1;
}
}
int par(int x){
if(t[x]<0)return x;
return t[x]=par(t[x]);
}
bool uni(int x,int y){
x=par(x);
y=par(y);
if(x==y)return false;
if(t[x]<t[y]){
t[x]+=t[y];
t[y]=x;
}
else{
t[y]+=t[x];
t[x]=y;
}
return true;
}
};
int phase,p[4];
UF uf,up[4];
int c[1000000],res;
bool b[4];
vector<int>e[1000000];
void Init(int N) {
res=N;
uf.init();
for(int i=0;i<4;i++){
up[i].init();
}
}
void Link(int A, int B) {
e[A].push_back(B);
e[B].push_back(A);
if(phase==0){
if(e[A].size()==3){
phase=2;
for(int i=0;i<3;i++){
p[i]=e[A][i];
}
p[3]=A;
for(int i=0;i<4;i++){
b[i]=true;
}
for(int i=0;i<4;i++){
for(int j=0;j<1000000;j++){
if(p[i]==j)continue;
int c=0;
for(int k:e[j]){
if(p[i]==k)continue;
c++;
if(j<k)continue;
if(!up[i].uni(j,k)){
b[i]=false;
}
}
if(c>=3)b[i]=false;
}
}
}
else if(e[B].size()==3){
phase=2;
for(int i=0;i<3;i++){
p[i]=e[B][i];
}
p[3]=B;
for(int i=0;i<4;i++){
b[i]=true;
}
for(int i=0;i<4;i++){
for(int j=0;j<1000000;j++){
if(p[i]==j)continue;
int c=0;
for(int k:e[j]){
if(p[i]==k)continue;
c++;
if(j<k)continue;
if(!up[i].uni(j,k)){
b[i]=false;
}
}
if(c>=3)b[i]=false;
}
}
}
else if(!uf.uni(A,B)){
phase=1;
res=-uf.t[uf.par(A)];
}
}
else if(phase==1){
if(e[A].size()==3){
phase=2;
for(int i=0;i<3;i++){
p[i]=e[A][i];
}
p[3]=A;
for(int i=0;i<4;i++){
b[i]=true;
}
for(int i=0;i<4;i++){
for(int j=0;j<1000000;j++){
if(p[i]==j)continue;
int c=0;
for(int k:e[j]){
if(p[i]==k)continue;
c++;
if(j<k)continue;
if(!up[i].uni(j,k)){
b[i]=false;
}
}
if(c>=3)b[i]=false;
}
}
}
else if(e[B].size()==3){
phase=2;
for(int i=0;i<3;i++){
p[i]=e[B][i];
}
p[3]=B;
for(int i=0;i<4;i++){
b[i]=true;
}
for(int i=0;i<4;i++){
for(int j=0;j<1000000;j++){
if(p[i]==j)continue;
int c=0;
for(int k:e[j]){
if(p[i]==k)continue;
c++;
if(j<k)continue;
if(!up[i].uni(j,k)){
b[i]=false;
}
}
if(c>=3)b[i]=false;
}
}
}
else if(!uf.uni(A,B)){
phase=3;
}
}
else if(phase==2){
for(int i=0;i<4;i++){
if(!b[i])continue;
if(A!=p[i]&&B!=p[i]){
if(!up[i].uni(A,B)){
b[i]=false;
}
int c=0;
for(int j:e[A]){
if(j!=p[i])c++;
}
if(c>=3)b[i]=false;
c=0;
for(int j:e[B]){
if(j!=p[i])c++;
}
if(c>=3)b[i]=false;
}
}
}
}
int CountCritical() {
if(phase==0)return res;
if(phase==1)return res;
if(phase==2){
res=0;
for(int i=0;i<4;i++){
res+=b[i];
}
return res;
}
return 0;
}
