#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<pair<int, int>>> adj(N), rev(N);
vector<int> out(N);
map<pair<int, int>, vector<int>> loc;
map<pair<int, int>, int> use;
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
rev[V[i]].emplace_back(U[i], i);
out[U[i]]++;
loc[{U[i], V[i]}].push_back(i);
}
// FIND ANY EDGE WITH DEGREE 2
int start = -1;
vector<int> ans;
if (out[0] >= 2) {
start = 0;
int left = adj[0][0].first;
int right = adj[0][1].first;
int a, b, c, d;
a = loc[{0, left}][use[{0, left}]++], b = loc[{left, 0}][use[{left, 0}]++];
c = loc[{0, right}][use[{0, right}]++], d = loc[{right, 0}][use[{right, 0}]++];
ans = {a, b, c, d, b, a, d, c};
return ans;
}
if (start == -1) {
vector<bool> vis(N);
vector<int> par(N, -1);
queue<int> q;
vis[0] = true;
q.emplace(0);
while (!q.empty()) {
auto u = q.front(); q.pop();
for (auto &[v, i] : adj[u]) {
if (!vis[v]) {
par[v] = u;
vis[v] = true;
q.emplace(v);
if (out[v] >= 3) {
start = v;
break;
}
}
}
}
if (start == -1) return false;
int at = start;
vector<int> path;
while (at != -1) {
// cerr << at sp par[at] << endl;
path.push_back(at);
at = par[at];
}
int m = path.size();
for (int i = m-1; i >= 1; i--) {
int u = path[i], v = path[i-1];
ans.push_back(loc[{u, v}].front());
use[{u, v}]++;
}
vector<int> cands;
bool ok = false;
for (int i = 0; i < adj[start].size(); i++) {
if (!ok and adj[start][i].first == par[start]) {
ok = true;
continue;
}
cands.push_back(adj[start][i].first);
}
int left = cands[0], right = cands[1];
int a, b, c, d;
a = loc[{start, left}][use[{start, left}]++], b = loc[{left, start}][use[{left, start}]++];
c = loc[{start, right}][use[{start, right}]++], d = loc[{right, start}][use[{right, start}]++];
vector<int> temp = {a, b, c, d, b, a, d, c};
for (auto &x : temp) ans.push_back(x);
for (int i = 0; i < m-1; i++) {
// cerr << i sp m-1 << endl;
int u = path[i], v = path[i+1];
ans.push_back(loc[{v, u}].front());
}
return ans;
}
return false;
}
