#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
variant<bool, vector<int>> ret;
if (N == 2) {
vector<vector<int>> boat(N);
for (int i=0;i<M;i++) {
boat[U[i]].push_back(i);
}
if (boat[0].size() < 2 || boat[1].size() < 1) {
ret = false;
ret = {};
return ret;
}
ret = true;
int f1 = boat[0][0], f2 = boat[0][1], s1 = boat[1][0];
ret = vector<int>({f1, s1, f2, f1, s1, f2});
return ret;
}
// check if subtask 2
if (N <= 400) {
vector<vector<int>> cnt(N, vector<int>(N, 0));
for (int i=0;i<M;i++) {
cnt[U[i]][V[i]]++;
}
bool ff=true;
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (i==j)continue;
if (cnt[i][j] == 0) ff=false;
}
}
if (ff) {
vector<int> f1(2), f2(2);
for (int i=0;i<M;i++) {
if (U[i] != 0 && V[i] != 0) continue;
if (U[i] == 1) f1[0] = i;
else if (V[i] == 1) f1[1]=i;
if (U[i] == 2) f2[0]=i;
else if (V[i] == 2) f2[1]=i;
}
ret = true;
ret = vector<int>({f1[0], f1[1], f2[0], f2[1], f1[1], f1[0], f2[1], f2[0]});
return ret;
}
}
return ret;
}
