#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
//#define endl '\n'
int n;
int co=0;
int st=0;
int par[1000001][5];
set<int> adj[1000001];
vector<int> dd;
int vis[4];
int find(int no,int ind){
if(par[no][ind]==no){
return no;
}
par[no][ind]=find(par[no][ind],ind);
return par[no][ind];
}
int ans;
void Init(int N_) {
n = N_;
for(int j=0;j<5;j++){
for(int i=0;i<n;i++){
par[i][j]=i;
}
}
ans=n;
}
vector<pair<int,int>> ed;
void push(int aa,int bb,int ind){
if(dd[ind-1]==aa or dd[ind-1]==bb){
return ;
}
int x=find(aa,ind);
int y=find(bb,ind);
if(x==y){
vis[ind-1]=1;
// cout<<dd[ind-1]<<":<<"<<endl;
// cout<<aa<"::"<<bb<<ind<<endl;
}
else{
par[x][ind]=y;
}
}
vector<int> path;
vector<int> cot;
int vis2[1000001];
void dfs(int no,int aa,int bb){
vis2[no]=1;
// cout<<no<<",";
cot.pb(no);
for(auto j:adj[no]){
if(no==aa and j==bb){
continue;
}
if(vis2[j]){
path=cot;
}
else{
dfs(j,aa,bb);
}
}
cot.pop_back();
}
void find3(int aa,int bb){
dfs(aa,aa,bb);
}
void Link(int aa, int bb){
ed.pb({aa,bb});
if(st){
for(int i=0;i<dd.size();i++){
push(aa,bb,i+1);
}
}
int prev=st;
/*if(st){
vector<int> dd;
int k=0;
for(auto j:cur){
k+=1;
if(j==aa or j==bb){
continue;
}
int x=find(aa,k);
int y=find(bb,k);
if(x==y){
dd.pb(j);
}
else{
par[x][j]=y;
}
}
for(auto j:dd){
cur.erase(j);
}
}*/
adj[aa].insert(bb);
// cout<<adj[aa].size()<<"...."<<endl;
if(adj[aa].size()==3){
if(st==0){
st=1;
dd.pb(aa);
for(auto j:adj[aa]){
dd.pb(j);
// cout<<j<<"<";
}
// cout<<endl;
}
else{
for(int i=0;i<dd.size();i++){
int stt=0;
if(dd[i]==aa){
stt=1;
}
for(auto j:adj[aa]){
if(dd[i]==j){
stt=1;
}
}
if(stt==0){
vis[i]=1;
// cout<<i<<"<........<"<<endl;
}
}
}
}
else if(adj[aa].size()==4){
if(st==0){
vis[1]=1;
vis[2]=1;
vis[3]=1;
dd.pb(aa);
st=1;
}
else{
for(int i=0;i<dd.size();i++){
if(dd[i]!=aa){
vis[i]=1;
}
}
}
}
swap(aa,bb);
adj[aa].insert(bb);
if(adj[aa].size()==3){
if(st==0){
st=1;
dd.pb(aa);
for(auto j:adj[aa]){
dd.pb(j);
}
}
else{
for(int i=0;i<dd.size();i++){
int stt=0;
if(dd[i]==aa){
stt=1;
}
for(auto j:adj[aa]){
if(dd[i]==j){
stt=1;
}
}
if(stt==0){
vis[i]=1;
// cout<<i<<"<........<"<<endl;
}
}
}
}
else if(adj[aa].size()==4){
if(st==0){
vis[1]=1;
vis[2]=1;
vis[3]=1;
dd.pb(aa);
st=1;
}
else{
for(int i=0;i<dd.size();i++){
if(dd[i]!=aa){
vis[i]=1;
}
}
}
}
// cout<<111<<"<"<<prev<<"<"<<st<<endl;
if(prev==0 and st==1){
// cout<<11<<endl;
for(int i=0;i<dd.size();i++){
// cout<<dd[i]<<"/";
for(auto j:ed){
push(j.a,j.b,i+1);
}
}
// cout<<endl;
}
if(st==0){
int x=find(aa,0);
int y=find(bb,0);
if(x!=y){
par[x][0]=y;
}
else{
co+=1;
if(co==1){
find3(aa,bb);
ans=path.size();
// cout<<endl;
}
else{
ans=0;
}
}
}
}
int CountCritical(){
if(ans==0){
return 0;
}
if(st){
int ans2=0;
for(int i=0;i<4;i++){
ans2+=1-vis[i];
}
return ans2;
}
else{
return ans;
}
}
int main() {
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;
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/
/*
g++ -DEVAL -Wall -static -O2 -o aa grader.cpp rings.cpp
*/
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:144:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:162:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:189:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
rings.cpp:199:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dd.size();i++){
~^~~~~~~~~~
/tmp/ccJBPR8Q.o: In function `main':
rings.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUWa0jh.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
