#include <vector>
#include <utility>
#define x first
#define y second
#define MAXN 1000009
std::vector < std::pair < int, int > > muchii;
std::vector < int > g[MAXN];
int n, ans, stare, t[MAXN], s[MAXN];
struct graf {
int interzis;
bool bines;
int t[MAXN], gr[MAXN];
};
std::vector < graf > grafuri;
int sef(int x, int t[]) {
if (t[x] == x) return x;
else return t[x] = sef(t[x], t);
}
inline void baga(graf &a, int x, int y) {
if (a.bines == 0)
return ;
if (x == a.interzis || y == a.interzis)
return ;
a.gr[x]++;
a.gr[y]++;
if (a.gr[x] >= 3 || a.gr[y] >= 3)
a.bines = 0;
x = sef(x, a.t);
y = sef(y, a.t);
if (x == y)
a.bines = 0;
else
a.t[x] = y;
}
inline void solve(graf &a) {
a.bines = 1;
for (int i = 0; i < n; i++)
a.t[i] = i, a.gr[i] = 0;
for (auto &x : muchii)
baga(a, x.x, x.y);
}
void Init(int N_) {
n = ans = N_;
for (int i = 0; i < ans; i++)
t[i] = i, s[i] = 1;
stare = 1;
}
void Link(int A, int B) {
if (stare == 4)
return ;
if (stare == 3) {
ans = 0;
for (auto &x : grafuri) {
baga(x, A, B);
ans += x.bines;
}
return ;
}
muchii.push_back({A, B});
g[A].push_back(B);
g[B].push_back(A);
if ((int)g[A].size() == 3 || (int)g[B].size() == 3) {
std::vector < int > noduri;
if ((int)g[A].size() == 3 && (int)g[B].size() == 3)
noduri.push_back(A), noduri.push_back(B);
else {
if ((int)g[A].size() < 3)
A = B;
noduri.push_back(A);
for (auto &x : g[A])
noduri.push_back(x);
}
stare = 3;
grafuri.resize(noduri.size());
for (int i = 0; i < (int)grafuri.size(); i++)
grafuri[i].interzis = noduri[i];
ans = 0;
for (auto &x : grafuri) {
solve(x);
ans += x.bines;
}
return ;
}
if (stare == 1) {
A = sef(A, t);
B = sef(B, t);
if (A == B)
ans = s[A], stare = 2;
else
t[A] = B, s[B] += s[A];
return ;
}
/// stare == 2
A = sef(A, t);
B = sef(B, t);
if (A == B)
ans = 0, stare = 4;
else
t[A] = B, s[B] += s[A];
}
int CountCritical() {
return ans;
}
