// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define X real()
#define Y imag()
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 4;
int n;
vector<int> adj[maxn];
vector<pii> E; pii delta;
int p[4][maxn], sz[4][maxn];
int numx[4], valx[4], R, Rx; pii val[4][maxn];
int get(int ind, int u) {
return p[ind][u] == u ? u : p[ind][u] = get(ind, p[ind][u]);
}
void merge(int ind, int ux, int vx) {
int u = get(ind, ux), v = get(ind, vx);
if (sz[ind][u] > sz[ind][v]) {
swap(ux, vx); swap(u, v);
}
if (u == v) {
numx[ind]++; Rx = sz[ind][v];
return ;
}
int u1 = val[ind][u].F, u2 = val[ind][u].S;
int v1 = val[ind][v].F, v2 = val[ind][v].S;
for (int T1 = 0; T1 < 2; T1++) {
for (int T2 = 0; T2 < 2; T2++) {
if (u2 == ux && v2 == vx) {
p[ind][u] = v; sz[ind][v] += sz[ind][u];
val[ind][v] = Mp(u1, v1);
return ;
}
swap(v1, v2);
}
swap(u1, u2);
}
numx[ind]++; Rx = sz[ind][v];
return ;
}
void build(int ind, int x) {
numx[ind] = 0; valx[ind] = x;
for (int i = 0; i < n; i++) {
p[ind][i] = i; sz[ind][i] = 1;
val[ind][i] = Mp(i, i);
}
for (auto f : E) {
int u = f.F, v = f.S;
if (u == valx[ind] || v == valx[ind]) continue;
merge(ind, u, v);
}
}
void rebuild3() {
int v = delta.S; R = 0;
build(R, v); R++;
for (int u : adj[v]) {
build(R, u); R++;
}
}
void rebuild4() {
int v = delta.S; R = 0;
build(R, v); R++;
}
void Init(int N) {
n = N; delta = Mp(0, 0);
R = 1; build(0, -1);
}
void Link(int u, int v) {
E.pb(Mp(u, v));
adj[u].pb(v); adj[v].pb(u);
for (int i = 0; i < R; i++) {
if (u == valx[i] || v == valx[i]) continue;
merge(i, u, v);
}
for (int x : {u, v}) {
if (len(adj[x]) > delta.F) {
delta = Mp(len(adj[x]), x);
if (delta.F == 3) rebuild3();
else if (delta.F == 4) rebuild4();
}
}
}
int CountCritical() {
if (delta.F <= 1) return n;
else if (delta.F == 2) {
if (numx[0] == 0) return n;
else if (numx[0] == 1) return Rx;
else return 0;
}
else {
int ans = 0;
for (int i = 0; i < R; i++) {
if (numx[i] == 0) ans++;
}
return ans;
}
}
