#include<bits/stdc++.h>
using namespace std;
int N;
vector<vector<int>> ed(1000005, (vector<int>){});
vector<int> cycles;
vector<int> possibles;
bool solvable = 1;
bool triple = 0;
int f[1000005];
int len[1000005];
void Init(int N_) {
for(int i = 0; i <= N_; ++i){
f[i] = i;
//cout << "init " << i << " " << f[i] << endl;
len[i] = 1;
}
N = N_;
}
int ffather(int no){
//cout << "check " << no << " " << f[no] << endl;
if(f[no] == no){
return no;
}
return f[no] = ffather(f[no]);
}
bool join(int u, int v){
u = ffather(u);
v = ffather(v);
if(u == v){
return 0;
}
if(len[v] > len[u]){
swap(u, v);
}
len[u] += len[v];
f[v] = u;
return 1;
}
void Link(int A, int B) {
ed[A].push_back(B);
ed[B].push_back(A);
if(solvable == 0){return;}
if((int)ed[A].size() == 4){
solvable = 0;
}
if((int)ed[B].size() == 4){
solvable = 0;
}
if(triple && (int)ed[A].size() == 3 || (int)ed[B].size() == 3){
unordered_map<int, int> m;
int need = 1;
for(auto e:possibles){
m[e]++;
}
if((int)ed[A].size() == 3){
need++;
m[A]++;
for(auto e:ed[A]){
m[e]++;
}
}
if((int)ed[B].size() == 3){
need++;
m[B]++;
for(auto e:ed[B]){
m[e]++;
}
}
possibles.clear();
for(auto e:m){
if(e.second == need){
possibles.push_back(e.first);
}
}
return;
}
if((int)ed[A].size() == 3 || (int)ed[B].size() == 3){
triple = 1;
unordered_map<int, int> m;
int need = 0;
if(ed[A].size() == 3){
need++;
m[A]++;
for(auto e:ed[A]){
m[e]++;
}
}
if(ed[B].size() == 3){
need++;
m[B]++;
for(auto e:ed[B]){
m[e]++;
}
}
possibles.clear();
for(auto e:m){
if(e.second == need){
possibles.push_back(e.first);
}
}
return;
}
if(!join(A, B)){
cycles.push_back(len[ffather(A)]);
return;
}
}
bool dfs(int no, int fat, int ex, vector<int> &vis){
if(no == ex){
return 1;
}
vis[no] = 1;
for(auto e:ed[no]){
if(e == fat)continue;
if(e == ex)continue;
if(vis[e] == 1){
return 0;
}
if(dfs(e, no, ex, vis) == 0){
return 0;
}
}
return 1;
}
bool check(int exclude){
vector<int> vis(1000005, 0);
bool ans = 1;
for(int i = 0; i < N; ++i){
if(!vis[i]){
ans &= dfs(i, -1, exclude, vis);
}
}
return ans;
}
int CountCritical() {
if(!solvable){
return 0;
}
if(triple){
int ans = 0;
for(auto e:possibles){
//cout << e << " ";
if(check(e)){
ans++;
}
}
//cout << endl;
return ans;
}else{
if((int)cycles.size() == 0){
return N;
}else if((int)cycles.size() == 1){
return cycles[0];
}else{
return 0;
}
}
return -1e9;
}
