#include "islands.h"
#include <variant>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> U, V;
int N, M;
vector<vector<int>> adj;
map<pair<int,int>,int> cm;
vector<int> path_to(int target) {
vector<bool> vis(N);
vector<int> prev(N);
queue<int> q;
q.push(0);
vis[0] = true;
prev[0] = -1;
while (!q.empty()) {
int x = q.front(); q.pop();
if (x == target) {
vector<int> sol;
while (x != -1) {
sol.push_back(x);
x = prev[x];
}
reverse(sol.begin(), sol.end());
return sol;
}
for (auto c : adj[x]) {
if (!vis[V[c]]) {
vis[V[c]] = true;
prev[V[c]] = x;
q.push(V[c]);
}
}
}
return {};
}
variant<bool, vector<int>> find_journey(
int N, int M, vector<int> U, vector<int> V) {
::U = U;
::V = V;
::N = N;
::M = M;
adj.resize(N);
for (int i = 0; i < M; i++)
adj[U[i]].push_back(i);
for (int i = 0; i < M; i++)
cm[{U[i], V[i]}] = i;
if (adj[0].size() >= 2) {
int c0 = adj[0][0];
int c1 = adj[0][1];
int t0 = V[c0];
int t1 = V[c1];
int c2 = cm[{t0,0}];
int c3 = cm[{t1,0}];
return vector<int>{c0,c1,c2,c3,c1,c0,c3,c2};
}
for (int i = 1; i < N; i++) {
if (adj[i].size() < 3) continue;
auto p = path_to(i);
if (p.empty()) continue;
vector<int> ret;
for (int j = 0; j < p.size() - 1; j++)
ret.push_back(cm[{p[j], p[j+1]}]);
int from = p[p.size()-2];
int t0 = i;
int ts[2];
for (int j=0, k=0; k < adj[i].size() && j < 2; k++) {
if (adj[i][k] == from) continue;
ts[j++] = adj[i][k];
}
int t1 = ts[0];
int t2 = ts[1];
int c0 = cm[{t0,t1}];
int c1 = cm[{t1,t0}];
int c2 = cm[{t0,t2}];
int c3 = cm[{t2,t0}];
vector<int> t{
c0, c1, c2, c3,
c1, c0, c3, c2
};
ret.insert(ret.end(), t.begin(), t.end());
for (int j = p.size()-2; j >= 0; j--)
ret.push_back(cm[{p[j], p[j+1]}]);
return ret;
}
return false;
}
