//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define pb push_back
const int MAXM = 1e6 + 5;
#define ff first
#define ss second
vector <int> v[MAXM];
int n, comp, cycle, san[MAXM], tr;
bool rem[MAXM], vis[MAXM], gir, birgezek;
int bol[MAXM], oo;
bool bolonok = 0;
vector <int> ayyr, ko;
void Init(int N) {
n = N;
}
void dfs (int x, int pr) {
vis[x] = 1;
for (int i : v[x]) {
if (rem[i] or i == pr) continue;
if (vis[i]) {
cycle = 1;
continue;
}
dfs (i, x);
}
}
void dfs1 (int x, int pr) {
san[x] = 1;
comp++;
for (int i : v[x]) {
if (i == pr or rem[i]) continue;
if (san[i]) {
cycle = 1;
continue;
}
dfs1 (i, x);
}
}
int CountCritical() {
if ((int)ko.sz > 1) return 0;
if (bolonok) return 0;
int jogap = 0;
if (!birgezek) {
for (int i = 0; i < n; ++i) {
if ((int)v[i].sz > 3) {
ayyr.clear();
ayyr.pb (i);
break;
}
}
if (ayyr.empty()) {
for (int i = 0; i < n; ++i) {
if ((int)v[i].sz == 3) {
ayyr.pb (i);
for (int j : v[i]) {
ayyr.pb (j);
}
break;
}
}
}
}
if (!ayyr.empty()) {
birgezek = 1;
for (int i : ayyr) {
rem[i] = 1;
cycle = 0;
for (int j = 0; j < n; ++j) {
san[j] = (int)v[j].sz;
}
for (int j = 0; j < n; ++j) {
if (rem[j] or vis[j]) continue;
dfs (j, -1);
}
for (int j : v[i]) {
san[j]--;
}
san[i] = 0;
bool aa = 0;
if (cycle) aa = 1;
for (int j = 0; j < n; ++j) {
if (san[j] > 2) aa = 1;
san[j] = vis[j] = 0;
}
rem[i] = 0;
if (!aa) {
jogap++;
}
}
if (!jogap) bolonok = 1;
return jogap;
}
else {
int opysy = 0;
int jogap1 = 0;
for (int i = 0; i < n; ++i) {
if (!san[i]) {
cycle = 0;
comp = 0;
dfs1 (i, -1);
opysy += cycle;
if (cycle) {
jogap = comp;
}
else {
jogap1 += comp;
}
}
}
for (int i = 0; i < n; ++i) {
san[i] = 0;
}
if (opysy > 1) {
bolonok = 1;
return 0;
}
else if (opysy == 1) return jogap;
else return jogap1;
}
return n;
}
void Link(int a, int b) {
v[a].pb (b);
v[b].pb (a);
if ((int)ko.sz > 1) return;
if ((int)v[a].sz > 3) {
if (ko.empty()) ko.pb (a);
else if (ko[0] != a) ko.pb (a);
}
if ((int)ko.sz > 1) return;
if ((int)v[b].sz > 3) {
if (ko.empty()) ko.pb (b);
else if (ko[0] != b) ko.pb (b);
}
}
//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//
//#define inbuf_len 1 << 16
//#define outbuf_len 1 << 16
//
//int main() {
// freopen("input3.txt", "r", stdin);
// int tmp;
//
// /* Set input and output buffering */
// char *inbuf, *outbuf;
// inbuf = (char*) malloc(inbuf_len * sizeof(char));
// outbuf = (char*) malloc(outbuf_len * sizeof(char));
// tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
// tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
//
// int N, L;
// tmp = scanf("%d %d", &N, &L);
// assert(tmp == 2);
// Init(N);
//
// int i;
// for (i = 0; i < L; i++) {
// int A, B;
// tmp = scanf("%d", &A);
// if (A == -1) {
// int critical;
// critical = CountCritical();
// printf("%d\n", critical);
// } else {
// tmp = scanf("%d", &B);
// assert(tmp == 1);
// Link(A, B);
// }
// }
//
// return 0;
//
//}
