#include<bits/stdc++.h>
using namespace std ;
#define F first
#define S second
const int N = 2e5+5 ;
const int M = 4e5+5 ;
int n , m , vis[M] , vis1[N] , vis2[N] ;
vector<pair<int,int>> nei[N] ;
vector<int> path ;
int GetMove();
void MakeMove(int v);
bool checkdfs(int node){
vis1[node] = 1 ;
for(auto it:nei[node]){
if(vis[it.S]) continue ;
if(it.F==1){
vis2[node] = 1 ; vis1[node] = 0 ; return true ;
}
if(vis1[it.F]) continue ;
vis[it.S] = 1 ;
if(checkdfs(it.F)){
vis1[node] = 0 ; return true ;
}
vis[it.S] = 0 ;
}
vis1[node] = 0 ;
return false ;
}
bool check(){
for(auto it:nei[1]){
if(vis[it.S] || vis2[it.F]) continue ;
vis[it.S] = 1 ; vis2[it.F] = 1 ;
if(!checkdfs(it.F)) return false ;
}
return true ;
}
bool dfs(int node){
path.push_back(node) ;
if(node==1) return true ;
for(auto it:nei[node]){
if(vis[it.S]) continue ;
vis[it.S] = 1 ;
if(dfs(it.F)) return true ;
vis[it.S] = 0 ;
}
path.pop_back() ;
return false ;
}
void SocialEngineering(int n1 , int m1 , vector<pair<int,int>> edges){
n = n1 , m = m1 ;
for(int i=0 ; i<m ; i++){
int u = edges[i].F , v = edges[i].S ;
nei[u].push_back({v,i}) ; nei[v].push_back({u,i}) ;
}
if(!check()) return ;
memset(vis,0,sizeof(vis)) ;
while(true){
int temp = GetMove() ;
for(auto it:nei[1]){
if(it.F==temp) vis[it.S] = 1 ;
}
bool flag = dfs(temp) ;
if(!flag) return ;
for(int i=1 ; i<path.size() ; i++) MakeMove(path[i]) ;
}
}
int main(){
return 0 ;
}
/*
int GetMove(){
cout << "GetMove\n" ;
int k ; cin >> k ; return k ;
}
void MakeMove(int v){
cout << "MakeMove: " << v << '\n' ;
}
int main(){
// SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}}) ;
SocialEngineering(2, 1, {{1,2}}) ;
return 0 ;
}
*/
