#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int> dfs(vector<bool> &visited, vector<int> &parents, vector<vector<int>> &adjacency1, vector<vector<int>> &adjacency2, int cur, int parent) {
visited[cur] = true;
parents[cur] = parent;
if (!adjacency2[cur].empty()) return {cur, -1};
for (int &child : adjacency1[cur]) {
if (child == parent) continue;
if (visited[child]) return {cur, child};
auto curRes = dfs(visited, parents, adjacency1, adjacency2, child, cur);
if (curRes.first != -1) return curRes;
}
return {-1, -1};
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
vector<vector<vector<int>>> adjacencyMatrix(N, vector<vector<int>>(N));
vector<vector<int>> adjacency1(N), adjacency2(N);
for (int i = 0; i < M; ++i) adjacencyMatrix[U[i]][V[i]].push_back(i);
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (adjacencyMatrix[i][j].size() == 1) adjacency1[i].push_back(j), adjacency1[j].push_back(i);
else if (adjacencyMatrix[i][j].size() > 1) adjacency2[i].push_back(j), adjacency2[j].push_back(i);
}
}
vector<bool> visited(N, false);
vector<int> parents(N, -1);
auto res = dfs(visited, parents, adjacency1, adjacency2, 0, -1);
if (res.first == -1) return false;
else return true;
vector<int> journey, cycle;
vector<bool> newVisited(N, false);
int cur = res.first;
while (cur != -1) {
journey.push_back(cur);
newVisited[cur] = true;
cur = parents[cur];
}
reverse(journey.begin(), journey.end());
if (res.second == -1) {
cycle.push_back(res.first);
cycle.push_back(adjacency2[res.first][0]);
} else {
vector<int> journey2;
int cur2 = res.second;
while (cur2 != -1) {
if (newVisited[cur2]) break;
journey2.push_back(cur2);
cur2 = parents[cur2];
}
reverse(journey2.begin(), journey2.end());
int i = 0;
while (journey[i] != cur2) ++i;
while (journey.size() > i) {
cycle.push_back(journey.back());
journey.pop_back();
}
journey.push_back(cur2);
reverse(cycle.begin(), cycle.end());
while (!journey2.empty()) {
cycle.push_back(journey2.back());
journey2.pop_back();
}
}
// for (int &i : journey) cout << i << ' ';
// cout << endl;
vector<int> ans;
int jSz = journey.size(), cSz = cycle.size();
for (int i = 0; i < jSz - 1; ++i) ans.push_back(adjacencyMatrix[journey[i]][journey[i + 1]][0]);
if (cSz == 2) {
int a = cycle[0], b = cycle[1];
ans.push_back(adjacencyMatrix[a][b][0]);
ans.push_back(adjacencyMatrix[b][a][0]);
ans.push_back(adjacencyMatrix[a][b][1]);
ans.push_back(adjacencyMatrix[a][b][0]);
ans.push_back(adjacencyMatrix[b][a][0]);
ans.push_back(adjacencyMatrix[a][b][1]);
} else {
cycle.push_back(cycle[0]);
vector<int> cycle2;
for (int &i : cycle) cycle2.push_back(i);
reverse(cycle2.begin(), cycle2.end());
// for (int &i : cycle) cout << i << ' ';
// cout << endl;
// for (int &i : cycle2) cout << i << ' ';
// cout << endl;
cSz = cycle.size();
for (int i = 0; i < cSz - 1; ++i) ans.push_back(adjacencyMatrix[cycle[i]][cycle[i + 1]][0]);
for (int i = 0; i < cSz - 1; ++i) ans.push_back(adjacencyMatrix[cycle2[i]][cycle2[i + 1]][0]);
for (int i = cSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[cycle[i]][cycle[i + 1]][0]);
for (int i = cSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[cycle2[i]][cycle2[i + 1]][0]);
}
for (int i = jSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[journey[i]][journey[i + 1]][0]);
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// srand(time({}));
// int n = 1000;
// int m = 100;
// for (int _ = 0; _ < 100; ++_) {
// vector<int> u, v;
// vector<int> curIn = {0};
// vector<bool> used(n, false);
// used[0] = true;
// for (int i = 0; i < m; ++i) {
// int cur = 0;
// while (used[cur]) cur = rand() % 1000;
// int connect = rand() % (curIn.size());
// u.push_back(cur); u.push_back(curIn[connect]);
// v.push_back(curIn[connect]); v.push_back(cur);
// used[cur] = true;
// curIn.push_back(cur);
// }
// u.push_back(curIn[1]); u.push_back(curIn[2]);
// v.push_back(curIn[2]); v.push_back(curIn[1]);
// cout << "TEST: " << _ << endl;
// for (int &i : u) cout << i << " ";
// cout << endl;
// for (int &i : v) cout << i << " ";
// cout << endl;
// auto res = find_journey(n, 2 * m + 2, u, v);
// if (res.index() == 0) {
// cout << "ERROR: BOOL" << endl;
// cout << get<bool>(res) << endl;
// break;
// // }
// // else if (get<bool>(res) == true) {
// // cout << "ERROR: output is TRUE" << endl;
// } else {
// cout << "SUCCESS" << endl;
// vector<int> x = get<vector<int>>(res);
// for (int &i : x) cout << i << ' ';
// cout << endl;
// }
// }
// return 0;
// }
