#include <algorithm>
#include <vector>
const int MAXN = 1e6;
int rings;
std::vector<int> graph[MAXN];
int parent[MAXN];
int ccSize[MAXN];
int candidate = -1;
int part = 0;
int last = -1;
bool isParticular[MAXN];
std::vector<int> listThree;
std::vector<int> listMore;
bool seen[MAXN];
bool adj[MAXN];
void Init(int N_)
{
rings = N_;
for (int iRing = 0; iRing < rings; iRing++)
{
parent[iRing] = iRing;
ccSize[iRing] = 1;
}
}
int find(int node)
{
if (node != parent[node])
parent[node] = find(parent[node]);
return parent[node];
}
void fillLists(int node)
{
if (seen[node])
return;
seen[node] = true;
if (graph[node].size() == 3)
listThree.emplace_back(node);
else if (graph[node].size() > 3)
listMore.emplace_back(node);
for (int next : graph[node])
fillLists(next);
}
int nogood(int node, int root)
{
if (seen[node])
return 0;
seen[node] = true;
int degOffset = 0;
for (int next : graph[node])
if (next == root)
degOffset++;
if (graph[node].size() - degOffset == 3)
return -1;
int ans = (graph[node].size() - degOffset <= 1);
for (int next : graph[node])
{
int sub = nogood(next, root);
if (sub == -1)
return -1;
ans |= sub;
}
return ans;
}
bool iscrit(int node)
{
if (adj[node])
return false;
adj[node] = true;
std::fill_n(seen, rings, false);
seen[node] = true;
for (int start : graph[node])
if (!seen[start] && nogood(start, node) < 1)
return false;
return true;
}
int check(int node)
{
listThree.clear();
listMore.clear();
std::fill_n(seen, rings, false);
std::fill_n(adj, rings, false);
fillLists(node);
if (listThree.empty() && listMore.empty())
return ccSize[node];
if (listMore.size() > 1)
{
candidate = -2;
return 0;
}
if (listMore.size() == 1)
{
if (iscrit(listMore[0]))
return 1;
candidate = -2;
return 0;
}
if (listThree.size() > 4)
{
candidate = -2;
return 0;
}
if (listThree.size() < 3)
{
int ans = 0;
for (int root : listThree)
{
ans += iscrit(root);
for (int nxt : graph[root])
ans += iscrit(nxt);
}
if (ans == 0)
candidate = -2;
return ans;
}
int ans = 0;
for (int root : listThree)
ans += iscrit(root);
if (ans == 0)
candidate = -2;
return ans;
}
void Link(int A, int B)
{
if (candidate == -2)
return;
int ccA = find(A);
int ccB = find(B);
graph[A].emplace_back(B);
graph[B].emplace_back(A);
if (ccA == ccB)
{
part += !isParticular[ccA];
isParticular[ccA] = true;
last = -1;
}
else
{
if (ccSize[ccA] < ccSize[ccB])
std::swap(ccA, ccB);
parent[ccB] = ccA;
ccSize[ccA] += ccSize[ccB];
if (isParticular[ccA] && isParticular[ccB])
{
part--;
last = -1;
}
isParticular[ccA] |= isParticular[ccB];
if (graph[A].size() == 3 || graph[A].size() == 4 || graph[B].size() == 3 || graph[B].size() == 4)
{
part += !isParticular[ccA];
isParticular[ccA] = true;
last = -1;
}
else if (graph[A].size() > 4 || graph[B].size() > 4)
{
isParticular[ccA] = true;
}
}
if (isParticular[ccA] && candidate != -2)
candidate = ccA;
}
int CountCritical()
{
if (candidate == -2)
return 0;
if (part == 0)
return rings;
if (part > 1)
return 0;
if (last == -1)
last = check(candidate);
return last;
}
