#include <bits/stdc++.h>
using namespace std;
struct DSU{
int n, cnt, idx;
vector<int> lab, cyc;
void init(int _n){
n=_n; cnt=0;
lab.assign(n+1, -1);
cyc.assign(n+1, 0);
idx=-1;
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
void union_sets(int u, int v){
u=find_set(u); v=find_set(v);
if (u!=v){
if (lab[u]>lab[v]) swap(u, v);
lab[u]+=lab[v];
lab[v]=u;
cnt-=cyc[u]; cnt-=cyc[v];
cnt+=(cyc[u]+=cyc[v]); cyc[v]=0;
}else cnt-=cyc[u], cnt+=(cyc[u]+=1);
if (cyc[u]) idx=u;
}
} dsu;
const int N=1e6+10;
int n, deg[N];
vector<pair<int, int>> edge;
bool check;
void Init(int N_) {
n=N_;
}
void build(int u){
check=1;
dsu.init(n);
for (auto &i:edge){
if (i.first==u || i.second==u) continue;
++deg[i.first]; ++deg[i.second];
check&=deg[i.first]<=2 && deg[i.second]<=2;
dsu.union_sets(i.first, i.second);
}
check&=dsu.cnt==0;
}
void Link(int u, int v) {
++u; ++v;
edge.emplace_back(u, v);
}
int CountCritical() {
int ans=0;
for (int i=1; i<=n; ++i) build(i), ans+=check;
return ans;
}
