#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// <|°_°|>
const int MAX_NOEUDS = (1000 * 1000);
int Dsu[4][MAX_NOEUDS];
int Deg[4][MAX_NOEUDS];
pair <int, int> Aretes[MAX_NOEUDS];
int nbAretes = 0;
bool IsCritical[4];
int NoeudOut[4];
int nbNoeuds;
bool isSplit = false;
int tailleCycle = 0;
int Find(int id, int a) {
if (Dsu[id][a] < 0)
return a;
return Dsu[id][a] = Find(id, Dsu[id][a]);
}
bool Union(int id, int nb) {
int rA = Find(id, Aretes[nb].first), rB = Find(id, Aretes[nb].second);
if (rA == rB)
return false;
if (Dsu[id][rA] > Dsu[id][rB])
swap(rA, rB);
Dsu[id][rA] += Dsu[id][rB];
Dsu[id][rB] = rA;
return true;
}
void ConstructWithout(int id, int noeud) {
IsCritical[id] = true;
NoeudOut[id] = noeud;
for (int i = 0; i < nbAretes; i ++)
{
if (noeud != Aretes[i].first && noeud != Aretes[i].second)
{
IsCritical[id] &= Union(id, i);
IsCritical[id] &= ++ Deg[id][Aretes[i].first] <= 2;
IsCritical[id] &= ++ Deg[id][Aretes[i].second] <= 2;
}
}
return;
}
void Reconstruct(int a) {
for (int i = 0; i < nbNoeuds; i ++)
{
Deg[0][i] = 0;
Dsu[0][i] = -1;
}
isSplit = true;
vector <int> nv;
nv.push_back(a);
for (int i = 0; i < nbAretes; i ++)
{
if (Aretes[i].first == a || Aretes[i].second == a)
nv.push_back(Aretes[i].second ^ Aretes[i].first ^ a);
}
for (int i = 0; i < 4; i ++)
{
ConstructWithout(i, nv[i]);
}
return;
}
void Init(int n) {
for (int i = 0; i < 4; i ++)
{
for (int j = 0; j < n; j ++)
{
Dsu[i][j] = -1;
}
}
nbNoeuds = n;
return;
}
void Link(int a, int b) {
Aretes[nbAretes ++] = {a, b};
if (!isSplit)
{
if (Deg[0][a] < Deg[0][b])
swap(a, b);
if (!Union(0, nbAretes - 1))
{
if (tailleCycle == 0)
tailleCycle = - Dsu[0][Find(0, a)];
else
tailleCycle = -1;
}
Deg[0][b] ++;
if (++ Deg[0][a] == 3)
Reconstruct(a);
}
else
{
for (int i = 0; i < 4; i ++)
{
if (NoeudOut[i] != a && NoeudOut[i] != b)
{
IsCritical[i] &= ++ Deg[i][a] <= 2;
IsCritical[i] &= ++ Deg[i][b] <= 2;
IsCritical[i] &= Union(i, nbAretes - 1);
}
}
}
return;
}
int CountCritical() {
if (!isSplit)
{
if (tailleCycle == 0)
return nbNoeuds;
if (tailleCycle > 0)
return tailleCycle;
return 0;
}
int nb = 0;
for (int i = 0; i < 4; i ++)
{
nb += IsCritical[i];
}
return nb;
}
