#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> E[200200];
set<pair<int, int>> adj[100100], INV[100100];
vector<int> deg0, ansf, ansb;
int n, s, on[100100], visited[100100];
vector<int> operator + (const vector<int> &a, const vector<int> &b){
vector<int> ret = a;
for (auto &x:b) ret.push_back(x);
return ret;
}
vector<int> rev(vector<int> a){
reverse(a.begin(), a.end()); return a;
}
void _erase(int x){
if (!on[x]) return;
on[x] = 0;
for (auto &[v, i]:INV[x]){
adj[v].erase(adj[v].find(make_pair(x, i)));
if (adj[v].empty()) deg0.push_back(v);
}
for (auto &[v, i]:adj[x]) INV[v].erase(INV[v].find(make_pair(x, i)));
}
void flip(int i){
auto [u, v] = E[i];
adj[u].erase(adj[u].find(make_pair(v, i))); INV[u].emplace(v, i);
INV[v].erase(INV[v].find(make_pair(u, i))); adj[v].emplace(u, i);
}
pair<vector<int>, vector<int>> solve(){
int cur = s;
vector<int> ret1;
while(!visited[cur]){
visited[cur] = 1;
ret1.push_back(adj[cur].begin()->second);
cur = adj[cur].begin()->first;
}
auto iter = find(ret1.begin(), ret1.end(), adj[cur].begin()->second);
vector<int> ret2(iter, ret1.end());
ret1.erase(iter, ret1.end());
return {ret1, ret2};
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
n = N, s = 1;
fill(on+1, on+n+1, 1);
for (int i=0;i<M;i++){
++U[i], ++V[i];
adj[U[i]].emplace(V[i], i+1);
INV[V[i]].emplace(U[i], i+1);
E[i+1] = {U[i], V[i]};
}
for (int i=1;i<=n;i++) if (adj[i].empty()) deg0.push_back(i);
while(true){
while(!deg0.empty()){
int x = deg0.back(); deg0.pop_back();
_erase(x);
}
if (!on[s]) return false;
if (adj[s].size()>1) break;
ansf.push_back(adj[s].begin()->second);
ansb.push_back(adj[s].begin()->second);
int nxt = adj[s].begin()->first;
_erase(s);
s = nxt;
}
auto [p1, c1] = solve();
adj[s].erase(adj[s].begin());
fill(visited+1, visited+n+1, 0);
for (auto &x:c1) flip(x);
auto [p2, c2] = solve();
auto ans = ansf + p1 + c1 + rev(p1) + p2 + c2 + rev(p2)+ p1 + rev(c1) + rev(p2) + p2 + rev(c2) + rev(p2) + rev(ansb);
for (auto &x:ans) --x;
return ans;
}
