#include "islands.h"
#include <variant>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;
vector<pair<int, int>> adj[1005];
int ot(int k)
{
return k % 2 ? (k-1) : (k+1);
}
bool visited[100005]; //간선 방문 체크
bool vsv[1005]; //정점 방문 체크
bool visited2[1005];
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for (int i = 0; i < M / 2; i++) {
adj[U[2*i]].push_back(make_pair(V[2*i], i));
}
vector<int> vc;
int _end = -1;
function<void(int)> dfs = [&](int v)
{
vsv[v] = true;
visited2[v] = true;
for (pair<int, int> p:adj[v]) {
if (visited[p.second]) continue;
visited[p.second] = true;
vc.push_back(p.second);
if (vsv[p.first]) {
_end = p.first;
return;
}
if (visited2[p.first]) {
vc.pop_back();
visited[p.second] = false;
continue;
}
dfs(p.first);
if (_end != -1) return;
visited[p.second] = false;
vc.pop_back();
}
vsv[v] = false;
};
dfs(0);
if (_end == -1) {
return false;
}
vector<int> v1, v2;
bool flag = false;
for (int i = 0; i < (int)vc.size(); i++) {
if (U[2*vc[i]] == _end) flag = true;
if (flag) v2.push_back(vc[i]);
else v1.push_back(vc[i]);
}
vector<int> ans;
for (int i:v1) ans.push_back(2*i);
for (int i:v2) ans.push_back(2*i);
for (int i:v2) ans.push_back(2*i+1);
reverse(v2.begin(), v2.end());
for (int i:v2) ans.push_back(2*i);
for (int i:v2) ans.push_back(2*i+1);
reverse(v1.begin(), v1.end());
for (int i:v1) ans.push_back(2*i);
return ans;
}
