#include <bits/stdc++.h>
using namespace std;
class Dsu
{
protected:
vector<int> pai, sub, grau;
bool isCicle;
int maxGrau;
public:
Dsu (int N = 0) : pai(N), sub(N, 1), grau(N, 0), isCicle(0), maxGrau(0) {iota(pai.begin(), pai.end(), 0);}
int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y)
{
grau[x]++; grau[y]++;
maxGrau = max({maxGrau, grau[x], grau[y]});
x = find(x), y = find(y);
if (x == y) {isCicle = 1; return;}
if (sub[x] < sub[y]) swap(x, y);
pai[y] = x; sub[x] += sub[y];
}
bool isGood() {return !isCicle && (maxGrau < 3);}
};
vector<set<int>> grafo;
vector<int> pai, sub, grau;
vector<bool> isCicle;
int critNum = 0, cicleNum = 0, degreeNum = 0, degreeV;
vector<int> tam3;
vector<pair<int, int>> edges;
map<int, Dsu> without;
int N;
void Init(int _N)
{
N = _N;
pai.resize(N); iota(pai.begin(), pai.end(), 0);
sub.resize(N); fill(sub.begin(), sub.end(), 1);
grau.resize(N); fill(grau.begin(), grau.end(), 0);
isCicle.resize(N); fill(isCicle.begin(), isCicle.end(), false);
grafo.clear(); grafo.resize(N); edges.clear(); tam3.clear();
without.clear();
critNum = N, cicleNum = 0, degreeNum = 0;
}
int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void LinkCicle(int A, int B)
{
if (critNum == 0) return;
int P = find(A);
cicleNum -= isCicle[P];
isCicle[P] = 1;
cicleNum += isCicle[P];
if (cicleNum > 1) critNum = 0;
else critNum = sub[P];
}
void Link3(int A, int B)
{
if (tam3.size() > 3) {critNum = 0; return;}
set<int> poss(tam3.begin(), tam3.end());
for (auto x : tam3)
for (auto viz : grafo[x])
poss.insert(viz);
critNum = 0;
for (auto x : poss)
{
if (!without.count(x))
{
without[x] = Dsu(N);
auto &atual = without[x];
for (auto [i, j] : edges)
if (i != x && j != x)
atual.une(i, j);
}
else if (A != x && B != x) without[x].une(A, B);
critNum += without[x].isGood();
}
}
void LinkDegree(int A, int B)
{
if (A == degreeV || B == degreeV) return;
without.begin()->second.une(A, B);
critNum = without.begin()->second.isGood();
}
void buildDegree()
{
without.clear();
without[degreeV] = Dsu(N);
for (auto [A, B] : edges) LinkDegree(A, B);
}
void Link(int A, int B)
{
edges.emplace_back(A, B);
if (critNum == 0) return;
if (degreeNum) {LinkDegree(A, B); return;}
grafo[A].insert(B), grafo[B].insert(A);
degreeNum -= (grau[A] >= 4), degreeNum -= (grau[B] >= 4);
grau[A]++; grau[B]++;
degreeNum += (grau[A] >= 4), degreeNum += (grau[B] >= 4);
if (degreeNum > 1) {critNum = 0; return;}
else if (degreeNum) {degreeV = (grau[A] >= 4 ? A : B); buildDegree(); return;}
if (grau[A] == 3) tam3.push_back(A);
if (grau[B] == 3) tam3.push_back(B);
if (!tam3.empty()) {Link3(A, B); return;}
int PA = find(A), PB = find(B);
if (PA == PB) {LinkCicle(A, B); return;}
if (sub[PA] < sub[PB]) swap(PA, PB);
pai[PB] = PA; sub[PA] += sub[PB]; isCicle[PA] = (isCicle[PA] || isCicle[PB]);
}
int CountCritical() {return critNum;}
