#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rettype variant<bool, vector<int>>
// global
int n, m;
const int mxN = 1e5 + 1;
vector<int> adj[mxN];
int par[mxN];
bool vis[mxN];
int vispos[mxN];
map<pii, int> mp;
vector<int> path;
bool done = false;
int loopstart = -1;
void dfs(int u = 0, int pp = -1) {
if (done) return;
vis[u] = true;
par[u] = pp;
vispos[u] = path.size();
path.pb(u);
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v, u);
if (done) return;
} else if (v != pp) {
loopstart = v;
done = true;
return;
}
}
path.pop_back();
vispos[u] = -1;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<int> u, v;
n = N; m = M; u = U; v = V;
if (n == 2) {
vector<int> hv[2];
for (int i = 0; i < m; i++) {
hv[u[i]].pb(i);
}
// cerr << "Checking: " << hv[0].size() << ' ' << hv[1].size() << endl;
if (hv[0].size() < 2 || hv[1].size() < 1) return false;
vector<int> ans;
ans.pb(hv[0][0]);
ans.pb(hv[1][0]);
ans.pb(hv[0][1]);
ans.pb(hv[0][0]);
ans.pb(hv[1][0]);
ans.pb(hv[0][1]);
return ans;
}
for (int i = 0; i < m; i++) {
mp[{u[i], v[i]}] = i;
}
for (pair<pii, int> cur : mp) {
adj[cur.ff.ff].pb(cur.ff.ss);
// adj[cur.ff.ss].pb(cur.ff.ff);
}
dfs();
if (loopstart == -1) return false;
// cerr << "loopstart " << loopstart << endl;
// for (int &cur : path) cerr << cur << ' ';
// cerr << endl;
vector<int> ans;
int looppos = vispos[loopstart];
int sz = path.size();
// cerr << "SIZE " << sz << endl;
for (int i = 0; i < looppos; i++) {
ans.pb(mp[{path[i], path[i + 1]}]);
}
for (int i = looppos; i < sz - 1; i++) {
ans.pb(mp[{path[i], path[i + 1]}]);
}
ans.pb(mp[{path[sz - 1], loopstart}]);
ans.pb(mp[{loopstart, path[sz - 1]}]);
for (int i = sz - 2; i >= looppos; i--) {
ans.pb(mp[{path[i + 1], path[i]}]);
}
ans.pb(mp[{path[sz - 1], loopstart}]);
for (int i = sz - 2; i >= looppos; i--) {
ans.pb(mp[{path[i], path[i + 1]}]);
}
for (int i = looppos; i < sz - 1; i++) {
ans.pb(mp[{path[i + 1], path[i]}]);
}
ans.pb(mp[{loopstart, path[sz - 1]}]);
for (int i = looppos - 1; i >= 0; i--) {
ans.pb(mp[{path[i], path[i + 1]}]);
}
return ans;
}
