#include "islands.h"
#include <iostream>
#include <map>
#include <variant>
#include <vector>
std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels);
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
std::vector<std::vector<int>> canoesfrom(N);
for (int i = 0; i < M; ++i) canoesfrom[U[i]].push_back(i);
std::vector<bool> seen(N);
std::vector<int> stack = {0};
while (!stack.empty()) {
int node = stack.back();
stack.pop_back();
if (seen[node]) continue;
seen[node] = true;
for (int i : canoesfrom[node]) {
stack.push_back(V[i]);
}
}
std::vector<int> newu, newv, original_labels;
int newm = 0;
for (int i = 0; i < N; ++i) {
if (!seen[i]) continue;
for (int out : canoesfrom[i]) {
newu.push_back(U[out]);
newv.push_back(V[out]);
original_labels.push_back(out);
++newm;
}
}
return find_journey_connected(N, newm, newu, newv, original_labels);
}
// everything except line case works
std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels) {
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back(i);
}
std::vector<int> ans;
auto dfs = [&](int node, int waka, auto dfs) -> bool {
std::vector<int> goodadj;
for (int to : adj[node]) {
if (waka != -1 && (original_labels[to] & (-2)) == (original_labels[waka] & (-2))) continue; // don't go back
goodadj.push_back(to);
}
if (goodadj.size() >= 2) {
ans.push_back(original_labels[goodadj[0]]);
ans.push_back(original_labels[goodadj[0]] ^ 1);
ans.push_back(original_labels[goodadj[1]]);
ans.push_back(original_labels[goodadj[1]] ^ 1);
ans.push_back(original_labels[goodadj[0]] ^ 1);
ans.push_back(original_labels[goodadj[0]]);
ans.push_back(original_labels[goodadj[1]] ^ 1);
ans.push_back(original_labels[goodadj[1]]);
return true;
}
for (int to : goodadj) {
ans.push_back(original_labels[to]);
if (dfs(V[to], to, dfs)) {
ans.push_back(original_labels[to]);
return true;
}
ans.pop_back();
}
return false;
};
bool exists = dfs(0, -1, dfs);
if (!exists) return false;
return ans;
}
