#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, cnt, lst, freq[1000010], p[1000010], deg[1000010], vis[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]);
}
void Init(int N) {
n = N;
for (int i = 0; i < n; i++) p[i] = i, 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 Link(int u, int v) {
lst = cnt;
edge[u].push_back(v);
edge[v].push_back(u);
if (dsu(u) == dsu(v)) {
if (found) {
cnt++;
freq[u]++;
freq[v]++;
} else {
dfs(u,u,-1);
cnt++;
for (int i = 0; i < cycle.size(); i++) freq[cycle[i]]++;
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() {
return pos.size();
}
