#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
const int M = 2e5 + 69;
vector <pair<int, int>> adj[N];
bool v1[N], vis[N];
int curr;
int n;
vector <int> path, ok[N], ok1;
pair <int, int> bruh[M];
void dfs(int u){
vis[u] = true;
for (auto [v, i] : adj[u]){
path.push_back(i);
if (v == curr && ok1.size() == 0){
ok1 = path;
} else if (!vis[v]){
dfs(v);
}
path.pop_back();
}
}
void dfs1(int u){
v1[u] = true;
ok[u] = path;
for (auto [v, i] : adj[u]){
if (!v1[v]){
path.push_back(i);
dfs1(v);
path.pop_back();
}
}
}
void add(vector <int> &a, vector <int> b, bool rev, int xo = 0){
if (rev) reverse(b.begin(), b.end());
for (auto x : b) a.push_back(x ^ xo);
}
vector <int> get(int i){
vector <int> ans;
int ong = 0;
add(ans, ok[i], false);
for (auto x : ans){
if (ong != bruh[x].first) assert(false);
ong = bruh[x].second;
swap(bruh[x].first, bruh[x].second);
}
add(ans, ok1, false);
for (auto x : ans){
if (ong != bruh[x].first) assert(false);
ong = bruh[x].second;
swap(bruh[x].first, bruh[x].second);
break;
}
add(ans, ok1, false, 1);
add(ans, ok1, true);
add(ans, ok1, true, 1);
add(ans, ok[i], true);
return ans;
}
variant<bool, vector<int>> find_journey(int nn, int m, vector<int> u, vector<int> v) {
n = nn;
for (int i = 0; i < m; i++){
bruh[i] = {u[i], v[i]};
}
for (int i = 0; i < m; i += 2){
adj[u[i]].push_back({v[i], i});
}
dfs1(0);
for (int i = 0; i < n; i++){
if (v1[i]){
curr = i;
//look for cycle starting and ending at i
//good if someone can reach curr
for (int j = 0; j < n; j++) vis[j] = false;
dfs(i);
if (ok1.size()) return get(i);
}
}
return false;
}
