#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);
REP(i, 0, M-2, 2) {
pairs[{U[i], V[i]}].push_back(i);
pairs[{V[i], U[i]}].push_back(i+1);
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
vt<int> ans, seen(N);
const auto dfs = [&](auto &&self, const int i) -> bool {
for (const auto &j : adj[i]) {
const ari2 bruh = {i, j}, bruh2 = {j, i};
if (size(pairs[bruh2]) > 1 && size(pairs[bruh]) > 1) {
const int a = pairs[{i, j}][0];
const int b = pairs[{i, j}][1];
const int c = pairs[{j, i}][0];
const int d = pairs[{j, i}][1];
ans.push_back(a);
ans.push_back(b);
ans.push_back(c);
ans.push_back(d);
ans.push_back(b);
ans.push_back(a);
ans.push_back(d);
ans.push_back(c);
return true;
}
ans.push_back(pairs[{i, j}][0]);
if (self(self, j))
return true;
ans.pop_back();
}
return false;
};
if (dfs(dfs, 0))
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;
}
