// In the name of Allah
#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 2e5 + 7;
int n, m;
vector<pii> adj[maxn], adjr[maxn];
int D[maxn]; queue<int> qu;
int mark[maxn]; vector<int> E;
vector<int> res, vc;
int M[maxn], cnt;
void fix_vc() {
while (!qu.empty()) {
int v = qu.front(); qu.pop();
for (auto f : adjr[v]) {
int u = f.F, j = f.S;
if (D[u] == 0) continue;
else if (D[u] == 1) qu.push(u);
D[u]--;
}
}
}
void checkx(int vx, int i) {
int v = vx; mark[v] = 1;
auto f = adj[v][i];
v = f.F; E.pb(f.S);
while (!mark[v]) {
mark[v] = 1;
auto f = adj[v][0];
v = f.F; E.pb(f.S);
}
}
int get_next(int v) {
for (auto f : adj[v]) {
int u = f.F, j = f.S;
if (len(res) >= 1 && res.back() == j) continue;
if (!M[j]) {
M[j] = 1; cnt++;
res.pb(j);
return u;
}
}
for (auto f : adjr[v]) {
int u = f.F, j = f.S;
if (len(res) >= 1 && res.back() == j) continue;
if (M[j]) {
M[j] = 0; cnt--;
res.pb(j);
return u;
}
}
return -1;
}
void get_ans(int vx) {
int v = vx;
while (true) {
v = get_next(v);
if (v == vx && cnt == 0) return ;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n = N; m = M;
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i]; D[u]++;
adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
}
for (int i = 0; i < n; i++) {
if (D[i] == 0) {
qu.push(i); D[i] = 0;
}
}
fix_vc();
int vx = 0;
while (D[vx] <= 1) {
if (D[vx] == 0) return false;
int ux = -1, i = -1;
for (auto f : adj[vx]) {
int u = f.F, j = f.S;
if (D[u] != 0) {
ux = u; i = j;
}
}
vc.pb(i);
qu.push(vx); D[vx] = 0;
fix_vc(); vx = ux;
}
for (int i = 0; i < n; i++) {
adj[i].clear(); adjr[i].clear();
}
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i];
if (D[u] == 0 || D[v] == 0) continue;
adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
}
for (int j : vc) res.pb(j);
checkx(vx, 0); checkx(vx, 1);
for (int i = 0; i < n; i++) {
adj[i].clear(); adjr[i].clear();
}
for (int i : E) {
int u = U[i], v = V[i];
if (D[u] == 0 || D[v] == 0) continue;
adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
}
get_ans(vx);
reverse(all(vc));
for (int j : vc) res.pb(j);
return res;
}
