#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define var variant
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 1e5 + 5;
int n, m;
arr<vec<int>, N> adj;
map<pii, int> id;
vec<int> stk, cyc;
arr<int, N> vs;
bool dfs(int u = 1) {
vs[u] = 1, stk.push_back(u);
for (int v : adj[u]) {
if (vs[v] == 2) continue;
if (vs[v] == 0) {
if (dfs(v)) return true;
continue;
}
while (true) {
int w = stk.back(); stk.pop_back();
cyc.push_back(w);
if (w == v) break;
}
stk.push_back(v);
reverse(cyc.begin(), cyc.end());
return true;
}
vs[u] = 2, stk.pop_back();
return false;
}
vec<int> ap(vec<int> x, vec<int> y) {
vec<int> ans = x;
ans.insert(ans.end(), y.begin(), y.end());
return ans;
}
vec<int> rv(vec<int> x) {
vec<int> ans = x;
reverse(ans.begin(), ans.end());
return ans;
}
vec<int> op(vec<int> x) {
vec<int> ans;
for (int i : x) {
if (i % 2 == 0) ans.push_back(i + 1);
else ans.push_back(i - 1);
}
return ans;
}
var<bool, vec<int>> find_journey(int _n, int _m, vec<int> _u, vec<int> _v) {
n = _n, m = _m;
for (int i = 0; i < m; i++) {
int u = _u[i] + 1, v = _v[i] + 1;
adj[u].push_back(v);
id[{u, v}] = i;
}
if (!dfs()) return false;
// for (int u : stk) cout << u << " ";
// cout << '\n';
// for (int u : cyc) cout << u << " ";
// cout << '\n';
vec<int> x, y;
for (int i = 0; i < stk.size(); i++)
if (i + 1 != stk.size()) x.push_back(id[{stk[i], stk[i + 1]}]);
for (int i = 0; i < cyc.size(); i++)
y.push_back(id[{cyc[i], cyc[(i + 1) % cyc.size()]}]);
if (stk.size() == 1) {
vec<int> ans;
ans = ap(ans, y);
ans = ap(ans, op(y));
ans = ap(ans, rv(y));
ans = ap(ans, op(rv(y)));
return ans;
}
vec<int> ans;
ans = ap(ans, x);
ans = ap(ans, y);
ans = ap(ans, rv(x));
ans = ap(ans, op(x));
ans = ap(ans, rv(y));
ans = ap(ans, rv(op(x)));
return ans;
}
