#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
variant<bool, vt<int>> find_journey(int N, int M, vt<int> U, vt<int> V) {
if (N == 2) {
vt<vt<int>> v(2);
FOR(i, 0, M-1)
v[U[i]].push_back(i);
if (size(v[0]) < 2 || size(v[1]) < 1)
return false;
const int a = v[0][0], b = v[0][1], c = v[1][0];
return vt<int>{a, c, b, a, c, b};
}
bool sub4 = true;
REP(i, 0, M-2, 2)
sub4 &= U[i] == U[i+1] && V[i] == V[i+1];
if (!sub4) {
map<ari2, vt<int>> pairs;
vt<vt<int>> adj(N);
FOR(i, 0, M-1) {
pairs[{U[i], V[i]}].push_back(i);
adj[U[i]].push_back(V[i]);
}
vt<int> ans, seen(N);
const auto dfs = [&](auto &&self, const int i, const int p) -> bool {
seen[i] = 1;
for (const auto &j : adj[i]) {
if (seen[j])
continue;
ans.push_back(pairs[{i, j}][0]);
if (self(self, j, i)) {
ans.push_back(pairs[{i, j}][0]);
return true;
}
ans.pop_back();
}
vt<int> va, vb;
for (const auto &j : adj[i]) {
if (j == p)
continue;
const ari2 bruh1 = {i, j}, bruh2 = {j, i};
if (size(pairs[bruh1]) > 1) {
va = {pairs[bruh1][0], pairs[bruh1][1]};
vb = {pairs[bruh2][0], pairs[bruh2][1]};
} else if (size(pairs[bruh1])) {
va.push_back(pairs[bruh1][0]);
vb.push_back(pairs[bruh2][0]);
}
if (size(va) == 2)
break;
}
if (size(va) == 2) {
vt<int> v = {va[0], vb[0], va[1], vb[1], vb[0], va[0], vb[1], va[1]};
ans.insert(ans.end(), all(v));
return true;
}
return false;
};
if (dfs(dfs, 0, -1))
return ans;
return false;
}
if (sub4) {
map<ari2, vt<int>> pairs;
vt<vt<int>> adj(N);
REP(i, 0, M-2, 2) {
pairs[{U[i], V[i]}].push_back(i);
pairs[{U[i], V[i]}].push_back(i+1);
adj[U[i]].push_back(V[i]);
}
vt<int> ans, seen(N), par(N), in_cyc(N);
const auto dfs = [&](auto &&self, const int i) -> bool {
seen[i] = 1;
for (const auto &j : adj[i]) {
if (seen[j] == 2)
continue;
if (seen[j] == 1) {
#ifdef DEBUG
cout << "cycle:";
for (int x = i; x != j; x = par[x])
cout << ' ' << x;
cout << ' ' << j << '\n';
#endif
vt<int> A = {pairs[{i, j}][0]}, B = {pairs[{i, j}][1]};
for (int x = i; x != j; x = par[x]) {
in_cyc[x] = 1;
A.push_back(pairs[{par[x], x}][0]);
B.push_back(pairs[{par[x], x}][1]);
ans.pop_back();
}
in_cyc[j] = 1;
reverse(all(A));
reverse(all(B));
ans.insert(ans.end(), all(A));
ans.insert(ans.end(), all(B));
reverse(all(A));
reverse(all(B));
ans.insert(ans.end(), all(A));
ans.insert(ans.end(), all(B));
return true;
}
ans.push_back(pairs[{i, j}][0]);
par[j] = i;
if (self(self, j)) {
if (!in_cyc[i])
ans.push_back(pairs[{i, j}][0]);
return true;
}
ans.pop_back();
}
seen[i] = 2;
return false;
};
if (dfs(dfs, 0)) {
assert(size(ans) <= 2000000);
return ans;
}
return false;
}
return false;
}
