#include "islands.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
vector<int> join(vector<int> v, vector<int> o, bool rev = false) {
if(rev) reverse(all(o));
v.insert(v.end(), all(o));
return v;
}
vector<int> solve_bidir_loop(vector<int> cy, vector<int> yc) {
vector<int> res;
res = join(res, cy);
res = join(res, yc, true);
res = join(res, cy, true);
res = join(res, yc);
return res;
}
const int MAXN = 100'000;
const int MAXM = 200'000;
struct Edge { int from, to, eid, rid; };
ostream& operator<<(ostream& os, const Edge &e) {
os << "[" << e.from << " ";
os << "(" << e.eid << " <-> " << e.rid << ")";
os << " " << e.to << "]";
return os;
}
Edge edges[MAXM + 10];
vector<int> adj[MAXN + 10];
int pid[MAXN + 10];
int dep[MAXN + 10];
bool vis[MAXN + 10];
int owo;
vector<int> uwu;
void dfs(int n, int p, int d) {
vis[n] = true;
dep[n] = d;
vector<int> child;
for(auto &eid:adj[n]) if(eid != p) {
Edge e = edges[eid];
if(vis[e.to]) {
if(dep[e.to] < dep[n]) owo = eid;
} else {
pid[e.to] = eid;
dfs(e.to, e.rid, d + 1);
child.eb(eid);
}
}
if(sz(child) > 1) {
child.eb(n);
uwu = child;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
// if (N == 4) {
// return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
// }
// return false;
if(N == 2) {
vector<int> e0, e1;
For(i, 0, M - 1) {
if(U[i] == 0) e0.eb(i);
else e1.eb(i);
}
if(sz(e0) >= 2 && sz(e1) >= 1) {
int a = e0[0], b = e0[1];
int c = e1[0];
return vector<int>({b, c, a, b, c, a});
}
return false;
}
map<pii, int> mp;
For(i, 0, M - 1) {
int x = U[i], y = V[i];
if(mp.count(pii(y, x))) {
int j = mp[pii(y, x)];
mp.erase(pii(y, x));
adj[x].push_back(i);
adj[y].push_back(j);
edges[i] = {x, y, i, j};
edges[j] = {y, x, j, i};
} else {
mp[pii(x, y)] = i;
}
}
#ifdef NYAOWO
For(i, 0, M - 1) {
cerr << edges[i] << "\n";
}
#endif
owo = -1;
pid[0] = -1;
dfs(0, -1, 1);
if(owo >= 0) {
// For(i, 0, N - 1) {
// cerr << pid[i] << " \n"[i == N - 1];
// }
// cerr << "owo: " << owo << "\n";
// return false;
int x = edges[owo].from; // lower
int y = edges[owo].to; // upper
vector<int> chain;
vector<int> cy, yc;
{
int cur = y;
while(cur != 0) {
auto e = edges[pid[cur]];
chain.eb(e.eid);
cur = e.from;
}
reverse(all(chain));
}
{
cy.eb(edges[owo].eid);
yc.eb(edges[owo].rid);
int cur = x;
while(cur != y) {
auto e = edges[pid[cur]];
cy.eb(e.eid);
yc.eb(e.rid);
cur = e.from;
}
reverse(all(cy));
reverse(all(yc));
}
vector<int> ans;
ans = join(ans, chain);
ans = join(ans, solve_bidir_loop(cy, yc));
ans = join(ans, chain, true);
return ans;
}
if(sz(uwu)) {
int x = uwu.back(); uwu.pop_back();
vector<int> chain;
{
int cur = x;
while(cur != 0) {
auto e = edges[pid[cur]];
chain.eb(e.eid);
cur = e.from;
}
reverse(all(chain));
}
int a = edges[uwu[0]].eid;
int c = edges[a].rid;
int b = edges[uwu[1]].eid;
int d = edges[b].rid;
vector<int> cyc = {a, c, b, d, c, a, d, b};
vector<int> ans;
ans = join(ans, chain);
ans = join(ans, cyc);
ans = join(ans, chain, true);
return ans;
}
return false;
}
/*
4 5
0 1
1 2
2 3
0 3
3 1
1
10
0 1 2 4 0 3 2 1 4 3
2 3
0 1
1 0
1 0
0
0
*/
