#include <bits/stdc++.h>
using namespace std;
int reverse_edge(int ind){
if(ind % 2 == 0) return ind+1;
else return ind-1;
}
std::variant<bool, std::vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
//case 1; multiple edge through 0
vector<int> e0(n,-1);
int a=-1, b=-1;
for(int i=0; i<m; ++i){
if(u[i] == 0){
if(e0[v[i]] != -1){
a = e0[v[i]]; b = i; break;
}
}
}
return vector<int>{a, reverse_edge(a), b, reverse_edge(b), reverse_edge(a), a, reverse_edge(b), b};
//case 2; do a simple cycle
vector<pair<int,int>> adj[n];
for(int i=0; i<m; i+=2){
adj[u[i]].push_back(make_pair(v[i],i));
adj[v[i]].push_back(make_pair(u[i],i+1));
}
//find cycle
vector<int> prev(n,-1), st(1,0);
vector<bool> vis(n, false);
bool found = false;
while(!st.empty()){
int v = st[st.size()-1];
st.pop_back();
vis[v] = true;
for(pair<int,int> p : adj[v]){
int u = p.first;
if(u==0 && prev[v]/2 != p.second/2){
found = true;
prev[0] = p.second;
break;
}
if(vis[u]) continue;
prev[u] = p.second;
st.push_back(u);
}
if(found) break;
}
if(!found) return false;
vector<int> cyc;
int x = 0;
do{
cyc.push_back(prev[x]);
x = u[prev[x]];
}while(x != 0);
reverse(cyc.begin(), cyc.end());
//now print the journey
vector<int> c;
for(int e : cyc){
c.push_back(e);
}
for(int e : cyc){
c.push_back(reverse_edge(e));
}
reverse(cyc.begin(), cyc.end());
for(int e : cyc){
c.push_back(e);
}
for(int e : cyc){
c.push_back(reverse_edge(e));
}
return c;
}
