#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<pair<int,int>>g[N];
int used[N];
deque<int>path;
int inv(int x){
if(x%2==0){
return x+1;
}
return x-1;
}
bool dfs(int v){
if(used[v]==1)return true;
if(used[v]==2)return false;
used[v]=1;
// if(g[v].size()>=3){
// if(used[g[v][0].ff])swap(g[v][0],g[v][1]);
// if(used[g[v][1].ff])swap(g[v][1],g[v][2]);
// path.push_back(g[v][0].ss);
// path.push_back(inv(g[v][0].ss));
// path.push_back(g[v][1].ss);
// path.push_back(inv(g[v][1].ss));
// path.push_back(inv(g[v][0].ss));
// path.push_back(g[v][0].ss);
// path.push_back(inv(g[v][1].ss));
// path.push_back(g[v][1].ss);
// return true;
// }
for(pair<int,int> to:g[v]){
if(dfs(to.ff)){
// path.push_front(to.ss);
// path.push_back(to.ss);
return true;
}
}
used[v]=2;
return false;
}
variant<bool, vector<int>> find_journey(int NN, int MM, vector<int> U, vector<int> V) {
n=NN;
m=MM;
// vector<int>from0(n,0),to0(n,0);
for(int i=0;i<m;i+=2){
g[U[i]].push_back({V[i],i});
// if(U[i]==0)from0[V[i]]=i;
// if(V[i]==0)to0[U[i]]=i;
}
// if(g[0].size()>=2){
// vector<int>ans = {from0[g[0][0].ff],to0[g[0][0].ff],
// from0[g[0][1].ff],to0[g[0][1].ff],
// to0[g[0][0].ff],from0[g[0][0].ff],
// to0[g[0][1].ff],from0[g[0][1].ff]};
// return ans;
// }
if(dfs(0)){
// vector<int>ans;
// for(int x:path)ans.push_back(x);
return true;
}
return false;
}
