#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, cnt, lst, freq[1000010], p[1000010], p2[1000010], deg[1000010], vis[1000010], is[1000010], from[1000010];
bool found, done;
vector<int> edge[1000010], pos, tmp, path, cycle;
int dsu(int u) {
if (p[u] == u) return u;
return p[u] = dsu(p[u]);
}
int dsu2(int u) {
if (p2[u] == u) return u;
return p2[u] = dsu(p2[u]);
}
void Init(int N) {
n = N;
for (int i = 0; i < n; i++) p[i] = p2[i] = i, from[i] = -1, pos.push_back(i);
}
void dfs(int u, int tar, int v) {
if (vis[u]) {
if (u == tar) cycle = path;
return;
}
path.push_back(u);
vis[u] = 1;
for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],tar,u);
path.pop_back();
}
void dfs2(int u, int v, int root) {
from[u] = root;
for (int i = 0; i < edge[u].size(); i++) if ((!is[edge[u][i]]) && (edge[u][i] != v)) dfs2(edge[u][i],u,root);
}
void Link(int u, int v) {
if (done) return;
lst = cnt;
edge[u].push_back(v);
edge[v].push_back(u);
if (found) {
if (dsu2(u) == dsu2(v)) {
done = 1;
return;
}
if ((!is[u]) && (!is[v])) p2[dsu2(u)] = dsu2(v);
if ((from[u] != -1) && (from[v] != -1)) {
if (from[u] == from[v]) {
cnt++;
freq[from[u]]++;
} else if ((abs(is[from[u]]-is[from[v]]) == 1) || (abs((int)((is[from[u]]%cycle.size())-(is[from[v]]%cycle.size()))) == 1)) {
cnt++;
freq[from[u]]++;
freq[from[v]]++;
} else {
if ((!is[u]) || (!is[v])) {
done = 1;
return;
}
cnt++;
freq[u]++;
freq[v]++;
}
} else if (from[u] != -1) {
dfs2(v,u,from[u]);
} else if (from[v] != -1) {
dfs2(u,v,from[v]);
}
} else {
if (dsu(u) == dsu(v)) {
dfs(u,u,-1);
cnt++;
for (int i = 0; i < cycle.size(); i++) {
is[cycle[i]] = i+1;
freq[cycle[i]]++;
}
for (int i = 0; i < cycle.size(); i++) dfs2(cycle[i],-1,cycle[i]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < edge[i].size(); j++) {
if ((is[i]) || (is[edge[i][j]])) continue;
p2[dsu2(i)] = dsu2(edge[i][j]);
}
}
found = 1;
} else p[dsu(u)] = dsu(v);
}
deg[u]++; deg[v]++;
if (deg[u] >= 3) {
cnt++;
freq[u]++;
if (deg[u] == 3) for (int i = 0; i < edge[u].size(); i++) freq[edge[u][i]]++;
}
if (deg[v] >= 3) {
cnt++;
freq[v]++;
if (deg[v] == 3) for (int i = 0; i < edge[v].size(); i++) freq[edge[v][i]]++;
}
if (cnt != lst) {
tmp.clear();
for (int i = 0; i < pos.size(); i++) if (freq[pos[i]] == cnt) tmp.push_back(pos[i]);
pos = tmp;
}
}
int CountCritical() {
if (done) return 0;
return pos.size();
}
