#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1e6 + 5;
int n;
struct DSU {
int forb;
int dsu[nmax], area[nmax];
int grad[nmax];
bool fail = 0;
int f(int x) { return (dsu[x] == x? x : dsu[x] = f(dsu[x])); }
void unite(int x, int y) {
if(x == forb || y == forb) return;
// cerr << x << ' ' << y << ' ' << forb << '\t';
grad[x]++;
grad[y]++;
if(grad[x] > 2 || grad[y] > 2)
fail = 1;
x = f(x);
y = f(y);
// cerr << x << ' ' << y << '\n';
if(x == y) { fail = 1; return; }
dsu[x] = y;
area[y] += area[x];
}
void init(int n, vector<pii> edg, int interz = -1) {
forb = interz;
for(int i = 0; i < n; i++)
dsu[i] = i, area[i] = 1, grad[i] = 0;
for(auto [a, b] : edg)
unite(a, b);
}
bool query() { return !fail; }
};
namespace Finite {
int freq[nmax];
vector<DSU> dlist;
int mgrad = 0;
int precrez = n;
vector<pii> edg;
vector<int> g[nmax];
void init3(int a) {
dlist.clear();
for(auto x : g[a])
dlist.resize(sz(dlist) + 1),
dlist.back().init(n, edg, x);
dlist.resize(sz(dlist) + 1),
dlist.back().init(n, edg, a);
return;
}
void init4(int a) {
dlist.clear();
dlist.resize(sz(dlist) + 1),
dlist.back().init(n, edg, a);
return;
}
void upd(int a, int b) {
g[a].emplace_back(b);
g[b].emplace_back(a);
edg.emplace_back(a, b);
int fmgrad = mgrad;
freq[a]++;
freq[b]++;
mgrad = max({mgrad, freq[a], freq[b]});
if(fmgrad != mgrad) {
if(mgrad == 3)
init3(freq[a] == 3? a : b);
if(mgrad == 4)
init4(freq[a] == 4? a : b);
if(mgrad > 2) return;
}
if(mgrad == 2) {
// cerr << a << ' ' << b << '\n';
// cerr << dlist[0].f(a) << ' ' << dlist[0].f(b) << '\n';
if(dlist[0].f(a) == dlist[0].f(b)) {
if(precrez == n) {
// cerr << "lamborghini\n";
precrez = dlist[0].area[dlist[0].f(a)];
}
else
precrez = 0;
}
}
for(auto &x : dlist)
x.unite(a, b);
return;
}
int get() {
if(mgrad >= 3) {
int sum = 0;
for(auto &x : dlist)
sum += x.query();
return sum;
}
else
return precrez;
}
void init() {
precrez = n;
dlist.resize(1);
dlist.back().init(n, edg);
}
}
void Init(int N) {
n = N;
Finite::init();
}
void Link(int A, int B) {
Finite::upd(A, B);
//cerr << " > " << Finite::get() << '\n';
}
int CountCritical() {
//cerr << Finite::state << '\t';
return Finite::get();
}
