#if 0
#include <bits/stdc++.h>
using namespace std;
//#define TEST
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int len = 1e6;
int n, state, cycle, last, t;
int par[4][len], deg[4][len], sz[4][len], block[4][len], fine[4];
vector<int> adj[len];
vector<ii> edge;
int fin(int i){
if (par[t][i] == i) return i;
return par[t][i] = fin(par[t][i]);
}
void join(int i, int j){
i = fin(i), j = fin(j);
if (i == j) return;
if (sz[t][i] > sz[t][j])
sz[t][i] += sz[t][j], par[t][j] = i;
else
sz[t][j] += sz[t][i], par[t][i] = j;
}
void build(int u){
block[t][u] = 1;
for (int i = 0; i < n; i++)
par[t][i] = i, deg[t][i] = 0, sz[t][i] = 1;
fine[t] = 1;
for (int i = 0; i < edge.size(); i++){
int a = edge[i].fi, b = edge[i].se;
if (!fine[t] || block[t][a] || block[t][b]) continue;
if (deg[t][a] > 1 || deg[t][b] > 1 || fin(a) == fin(b))
fine[t] = 0;
deg[t][a]++, deg[t][b]++;
join(a, b);
}
}
void Init(int N){
n = N, state = 0, cycle = 0, last = 0, t = 0;
for (int i = 0; i < n; i++)
par[0][i] = i, deg[0][i] = 0, sz[0][i] = 1;
}
void Link(int a, int b){
edge.pb(mp(a, b));
if (state == 0){
adj[a].pb(b), adj[b].pb(a);
deg[0][a]++, deg[0][b]++;
if (deg[0][a] < deg[0][b])
swap(a, b);
if (deg[0][a] == 3){
state = 1;
t = 0, build(a);
t = 1, build(adj[a][0]);
t = 2, build(adj[a][1]);
t = 3, build(adj[a][2]);
}
else{
a = fin(a), b = fin(b);
if (a == b)
cycle++, last = sz[0][a];
else
join(a, b);
}
}
else{
for (t = 0; t < 4; t++){
if (!fine[t] || block[t][a] || block[t][b]) continue;
if (deg[t][a] > 1 || deg[t][b] > 1 || fin(a) == fin(b))
fine[t] = 0;
deg[t][a]++, deg[t][b]++;
join(a, b);
}
}
}
int CountCritical(){
int ans = 0;
if (state == 0){
if (cycle == 0) ans = n;
else if (cycle == 1) ans = last;
else ans = 0;
}
else{
for (int j = 0; j < 4; j++)
ans += fine[j];
}
return ans;
}
#ifdef TEST
int main() {
freopen("example.txt", "r", stdin);
int tmp;
/* Set input and output buffering */
char *inbuf, *outbuf;
inbuf = (char*) malloc((1 << 16) * sizeof(char));
outbuf = (char*) malloc((1 << 16) * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, (1 << 16));
tmp = setvbuf(stdout, outbuf, _IOFBF, (1 << 16));
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;
}
#endif // TEST
#else
#ifndef EVAL
#include "grader.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 1e6 + 5;
vector<int> gr[MAXN];
int deg[MAXN], neig3[MAXN];
int p[MAXN], sz[MAXN];
int n, numcc, total, curcycle;
int great_node, big;
map<int, int> cnt;
set<int> three;
bool visit[MAXN];
void Init(int _n) {
n = _n;
for (int i = 0; i < n; i++) {
neig3[i] = 0;
deg[i] = 0;
p[i] = -1;
sz[i] = 1;
gr[i].clear();
}
three.clear();
numcc = n;
total = n;
big = 0;
cnt.clear();
cnt[0] = n;
}
int fin(int x) {
return (p[x] == -1 ? x : p[x] = fin(p[x]));
}
inline void chval(int x, int add) {
if (deg[x] == 3)
three.erase(x);
cnt[deg[x]]--;
if (cnt[deg[x]] == 0)
cnt.erase(deg[x]);
deg[x] += add;
cnt[deg[x]]++;
if (deg[x] == 3)
three.insert(x);
}
void dfs(int u) {
visit[u] = true;
for (auto v : gr[u]) {
if (visit[v]) continue;
dfs(v);
}
}
bool check(int w) {
for (auto v : gr[w])
chval(v, -1);
memset(visit, false, sizeof visit);
visit[w] = true;
chval(w, -((int)gr[w].size() + 1));
assert(cnt[1] % 2 == 0);
int comps = cnt[0] + cnt[1] / 2;
int want = 0;
/*
int how_many = 0;
for (auto it : cnt) {
if (it.first > 3)
how_many += it.second;
}
*/
for (int u = 0; u < n; u++) {
if (!visit[u]) {
want++;
dfs(u);
}
}
chval(w, +((int)gr[w].size() + 1));
for (auto v : gr[w])
chval(v, +1);
return want == comps;// && how_many == 0;
}
char str[100];
void Link(int a, int b) {
//str[0] = '\0';
if (deg[a] == 3) {
for (auto v : gr[a])
neig3[v]--;
big++;
}
if (deg[b] == 3) {
for (auto v : gr[b])
neig3[v]--;
big++;
}
chval(a, +1);
chval(b, +1);
gr[a].pb(b);
gr[b].pb(a);
if (deg[a] == 3) {
for (auto v : gr[a])
neig3[v]++;
}
if (deg[b] == 3) {
for (auto v : gr[b])
neig3[v]++;
}
if (deg[a] > 3) {
great_node = a;
} else if (deg[b] > 3) {
great_node = b;
}
int ra = fin(a), rb = fin(b);
if (ra != rb) {
numcc--;
if (sz[ra] > sz[rb]) {
p[rb] = ra;
sz[ra] += sz[rb];
} else {
p[ra] = rb;
sz[rb] += sz[ra];
}
} else {
curcycle = sz[ra];
}
if (ra == rb) {
if (big == 1 && fin(great_node) != ra) {
total = 0;
return;
} else if (big == 0 && cnt[3] > 0 && fin(*three.begin()) != ra) {
total = 0;
return;
}
}
if (big == 0 && cnt[3] == 0) {
// everything is either a chain or a cycle
assert(cnt[1] % 2 == 0);
int comps = cnt[0] + cnt[1] / 2;
if (comps == numcc) {
// every component is a chain
total = n;
} else if (comps == numcc - 1) {
total = curcycle;
} else {
//sprintf(str, "IMPOSSIBLE");
total = 0;
}
} else if (big > 1 || (false && cnt[3] > 4)) {
/*if (big > 1) {
if (cnt[3] > 4)
sprintf(str, "big > 1 and cnt[3] > 4");
else
sprintf(str, "big > 1");
} else {
//sprintf(str, "cnt[3] > 4");
//sprintf(str, "cnt[0] = %d, cnt[1] = %d, cnt[2] = %d, cnt[3] = %d, cnt[4] = %d", cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]);
if (three.size() <= 5) {
for (auto it : three) {
sprintf(str + strlen(str), "%d ", it);
}
}
}*/
total = 0;
} else if (big == 1) {
if (neig3[great_node] != (int)three.size()) {
//sprintf(str, "impossible great_node");
total = 0;
} else {
bool found = (great_node == a || great_node == b);
for (auto v : gr[a])
if (v == great_node)
found = true;
for (auto v : gr[b])
if (v == great_node)
found = true;
if (found || (ra == rb && total > 0)) {
if (check(great_node)) {
total = 1;
} else {
total = 0;
//sprintf(str, "no great_node");
}
}
}
} else if (big == 0 && cnt[3] > 0) {
// now big = 0 and cnt[3] > 0
const int c = (int)three.size();
set<int> proc;
for (auto u : three) {
proc.insert(u);
for (auto v : gr[u])
proc.insert(v);
}
bool found = false;
for (auto it : proc) {
if (it == a || it == b)
found = true;
}
if (found || (ra == rb && total > 0)) {
total = 0;
for (auto u : proc) {
if (deg[u] == 3 && neig3[u] == c - 1) {
if (check(u))
total++;
} else if (deg[u] < 3 && neig3[u] == c) {
if (check(u))
total++;
}
}
/*
if (total == 0)
sprintf(str, "no valid 3-degree nodes");
else
sprintf(str, "there are 3-degree nodes");
*/
}
/* else {
if (ra != rb || total == 0) return;
total = 0;
for (auto u : proc) {
if (deg[u] == 3 && neig3[u] == c - 1) {
if (check(u))
total++;
} else if (deg[u] < 3 && neig3[u] == c) {
if (check(u))
total++;
}
}
}*/
}
}
int CountCritical() {
//puts(str);
return total;
}
#endif
