#include "islands.h"
#include <variant>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
typedef variant<bool, vi> vbvi;
const int N = 100000, M = 200000;
int ij[M];
int *eh[N], eo[N], eo_[N], *fh[N], fo[N]; char deleted[N];
void append(int **eh, int *eo, int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
void dfs(int j) {
if (deleted[j] || eo_[j])
return;
deleted[j] = 1;
for (int o = fo[j]; o--; ) {
int h = fh[j][o], i = j ^ ij[h];
eo_[i]--, dfs(i);
}
}
int pp[N], ff[N]; char visited[N];
vi hh;
void circle(int i, int rev) {
if (visited[i]) {
if (!rev) {
int j = i;
do
hh.push_back(ff[j]);
while ((j = pp[j]) != i);
} else {
static int qu[N];
int j = i, cnt = 0;
do
qu[cnt++] = ff[j];
while ((j = pp[j]) != i);
while (cnt--)
hh.push_back(qu[cnt]);
}
return;
}
hh.push_back(ff[i]), circle(pp[i], rev), hh.push_back(ff[i]);
}
vbvi find_journey(int n, int m, vi ii, vi jj) {
for (int i = 0; i < n; i++) {
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
fh[i] = (int *) malloc(2 * sizeof *fh[i]);
}
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h];
ij[h] = i ^ j;
append(eh, eo, i, h), append(fh, fo, j, h), eo_[i]++;
}
for (int i = 0; i < n; i++)
dfs(i);
static int qu[N];
int u = 0, cnt = 0;
while (1) {
if (eo_[u] == 0)
return false;
if (eo_[u] >= 2)
break;
for (int o = eo[u]; o--; ) {
int h = eh[u][o], i = u ^ ij[h];
if (!deleted[i]) {
qu[cnt++] = h;
eo_[u] = 0, dfs(u);
u = i;
break;
}
}
}
memset(pp, -1, n * sizeof *pp), memset(ff, -1, n * sizeof *ff);
int v = -1, f = -1;
for (int i = 0; i < n; i++)
if (!deleted[i])
for (int o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
if (!deleted[j]) {
if (pp[i] == -1)
pp[i] = j, ff[i] = h;
else if (i == u)
v = j, f = h;
}
}
int i;
i = u;
while (!visited[i])
visited[i] = 1, i = pp[i];
while (visited[i] == 1)
visited[i] = 2, i = pp[i];
for (i = 0; i < n; i++)
if (visited[i] == 1)
visited[i] = 0;
i = v;
while (!visited[i])
visited[i] = 1, i = pp[i];
for (int h = 0; h < cnt; h++)
hh.push_back(qu[h]);
if (visited[i] == 2) {
for (i = 0; i < n; i++)
if (visited[i] == 1)
visited[i] = 0;
circle(u, 0), hh.push_back(f), circle(v, 1), hh.push_back(f);
} else {
while (visited[i] == 1)
visited[i] = 2, i = pp[i];
for (i = 0; i < n; i++)
if (visited[i] == 1)
visited[i] = 0;
circle(u, 0), hh.push_back(f), circle(v, 0), hh.push_back(f);
circle(u, 1), hh.push_back(f), circle(v, 1), hh.push_back(f);
}
for (int h = cnt - 1; h >= 0; h--)
hh.push_back(qu[h]);
return hh;
}
