#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
vector <vector <int>> graph;
bool in_cycle[1000007];
int n, cycles, cnt, used[1000007], used2[1000007], spcycle;
vector <int> st, to_be;
void dfs(int v, int p = -1){
st.pb(v);
used[v] = 1;
for(auto to : graph[v]){
if(p == to) continue;
if(used[to] == 1){
int flag = 0;
if(!cycles){
for(auto to2 : st){
if(to2 == to) flag = 1;
if(flag) in_cycle[to2] = 1;
}
}
cycles++;
}
else if(!used[to]){
dfs(to, v);
}
}
used[v] = 2;
st.pop_back();
}
void dfs2(int v, int p = -1){
used2[v] = 1;
cnt++;
if(in_cycle[v]) spcycle++;
for(auto to : graph[v]){
if(in_cycle[v] && !in_cycle[to]){
to_be.pb(to);
}
if(p == to) continue;
if(!used2[to]) dfs2(to, v);
}
}
void Init(int N) {
n = N;
graph.resize(n+1);
}
void Link(int A, int B) {
graph[A].pb(B);
graph[B].pb(A);
}
int CountCritical(){
int special[n];
for(int i = 0; i < n; i++){
used[i] = 0;
special[i] = 0;
used2[i] = 0;
in_cycle[i] = 0;
}
int fing_cycles = 0, saiz = 0;
for(int i = 0; i < n; i++){
if(!used[i]){
cycles = 0;
cnt = 0;
spcycle = 0;
to_be.clear();
st.clear();
dfs(i);
if(cycles == 1){
dfs2(i);
for(auto to : to_be) special[to] = 1;
if(cnt == spcycle){
fing_cycles++;
saiz = spcycle;
}
}
}
}
int initial = 0;
for(int i = 0; i < n; i++){
if(sz(graph[i]) > 2) initial++;
}
int ans = 0;
if(fing_cycles == 0){
// cout << initial << endl;
for(int i = 0; i < n; i++){
if(special[i]) continue;
int tmp = initial - (sz(graph[i]) > 2 ? 1 : 0);
for(auto to : graph[i]){
if(sz(graph[to]) == 3) tmp--;
}
if(!tmp){
ans++;
//cout << i << ' ' << sz(graph[i]) << endl;
// for(auto to : graph[i]){
// cout << to << ' ' << sz(graph[to]) << endl;
//}
//cout << 'a' << endl;
}
}
// cout << "NO FUCKING CYCLES" << endl;
}
else if(initial == 0){
if(fing_cycles > 1) return 0;
if(fing_cycles == 1) return saiz;
return n;
}
return ans;
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/
