#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 100023;
int par[N];
bool vis[N];
vector <int> a;
int c[N];
int sz[N];
vector <pair <int, int>> g[N], g2[N];
bool f[N], h[N];
void dfs1 (int v, int root) {
vis[v] = true;
if (root == 0)
f[v] = true;
for (auto [u, id] : g[v]) {
if (!vis[u]) {
dfs1 (u, root);
par[u] = id;
}
}
a.push_back(v);
}
void dfs2 (int v, int root) {
vis[v] = true;
c[v] = root;
sz[root]++;
for (auto [u, id] : g2[v]) {
if (!vis[u]) {
dfs2 (u, root);
}
}
}
pair <vector <int>, vector <int>> get (int i, int id) {
vector <int> v;
int x = i;
int y;
while (true) {
vis[x] = true;
int nx = -1;
int nxi = -1;
for (auto [u, in] : g[x]) {
if (h[u]) {
if (x == i && in == id) {
nx = u;
nxi = in;
} else if (x != i) {
nx = u;
nxi = in;
}
}
}
x = nx;
if (vis[nx]) {
y = nx;
break;
}
}
x = i;
vector <int> fi, se;
while (x != y) {
int nx = -1;
int nxi = -1;
for (auto [u, in] : g[x]) {
if (h[u]) {
if (x == i && in == id) {
nx = u;
nxi = in;
} else if (x != i) {
nx = u;
nxi = in;
}
}
}
x = nx;
fi.push_back(nxi);
}
x = y;
int cnt = 0;
while (x != y || cnt == 0) {
cnt++;
int nx = -1;
int nxi = -1;
for (auto [u, in] : g[x]) {
if (h[u]) {
if (x == i && in == id) {
nx = u;
nxi = in;
} else if (x != i) {
nx = u;
nxi = in;
}
}
}
x = nx;
se.push_back(nxi);
}
return make_pair (fi, se);
}
vector <int> merge (vector <int> a, vector <int> b) {
for (int x : b)
a.push_back(x);
return a;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
int n = N, m = M;
for (int i = 0; i < m; i++) {
g2[V[i]].push_back(make_pair (U[i], i));
g[U[i]].push_back(make_pair (V[i], i));
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs1 (i, i);
}
}
reverse (a.begin(), a.end());
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
vis[i] = false;
}
cout << '\n';
for (int i = 0; i < n; i++) {
if (!vis[a[i]])
dfs2 (a[i], a[i]);
}
for (int i = n - 1; i >= 0; i--) {
cout << c[i] << ' ';
if (sz[c[i]] >= 1)
h[c[i]] = true;
for (auto [j, id] : g[i]) {
h[c[i]] |= h[c[j]];
}
}
cout << endl;
for (int i = 0; i < n; i++) {
h[i] |= h[c[i]];
}
for (int i = 0; i < n; i++) {
if (f[i]) {
int cnt = 0;
vector <int> v;
for (auto [j, id] : g[i]) {
if (h[j]) {
cnt++;
v.push_back(id);
}
if (cnt == 2)
break;
}
if (cnt < 2)
continue;
vector <int> all, A, B, C, D, E;
int x = i;
while (x != 0) {
A.push_back (par[i]);
x = U[par[i]] ^ V[par[i]] ^ x;
}
reverse (A.begin(), A.end());
for (int i = 0; i < n; i++)
vis[i] = false;
pair <vector <int>, vector <int>> BB = get (i, v[0]);
for (int i = 0; i < n; i++)
vis[i] = false;
pair <vector <int>, vector <int>> DD = get (i, v[1]);
B = BB.F;
C = BB.S;
D = DD.F;
E = DD.S;
vector <int> nA, nB, nC, nD, nE;
nA = A;
nB = B;
nC = C;
nD = D;
nE = E;
reverse (nA.begin(), nA.end());
reverse (nB.begin(), nB.end());
reverse (nC.begin(), nC.end());
reverse (nD.begin(), nD.end());
reverse (nE.begin(), nE.end());
all = merge (all, A);
all = merge (all, B);
all = merge (all, C);
all = merge (all, nB);
all = merge (all, D);
all = merge (all, E);
all = merge (all, nD);
all = merge (all, B);
all = merge (all, nC);
all = merge (all, nB);
all = merge (all, D);
all = merge (all, nE);
all = merge (all, nD);
all = merge (all, nA);
return all;
}
}
return false;
}
