#include "islands.h"
#include<queue>
#include<cstring>
#include <variant>
#include <vector>
#include<set>
using namespace std;
#define NN 1005
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
vector<vector<int>> a(N);
for (int i = 0; i < M; ++i)
a[U[i]].push_back(i);
int is_sub2 = N<=400;
static int id[401][401];
if(N<=400){
memset(id, -1, sizeof id);
for(int i=0;i<M;++i)id[U[i]][V[i]]=i;
for(int i=0;i<N;++i)for(int j=i+1;j<N;++j)
if(id[i][j]==-1 ||id[j][i]==-1)is_sub2=0;
}
if (N==2){
if(a[0].size()>=2&&a[1].size()){
int a1=a[0][0],a2=a[0][1],a3=a[1][0];
return vector<int>{a1, a3, a2, a1, a3, a2};
}
return false;
}else if(is_sub2){
int a1=id[0][1],a2=id[1][0],a3=id[1][2],a4=id[2][1],a5=id[2][0],a6=id[0][2];
return vector<int>{a1,a3,a5,a6,a4,a2,a5,a3,a1,a2,a4,a6};
}else{
vector<vector<int>>g(N);
for (int i = 0; i < M; ++i) g[U[i]].push_back(V[i]);
vector<int> d(N,1e9);
vector<int>pare(N),cyclike(N);
queue<int>q;d[0]=0;q.push(0);while(q.size()){int u=q.front();q.pop();for(int v:g[u])if(d[v]>d[u]+1)d[v]=d[u]+1,q.push(v),pare[v]=u;}
vector<vector<int>>T(N);
for(int i=1;i<N;++i)T[pare[i]].push_back(i);
auto lca = [&](int u, int v) { while (d[u] - d[v]) if(d[u]<d[v])v=pare[v]; else u=pare[u]; while(u-v) u=pare[u],v=pare[v]; return u; };
multiset<pair<int, int > > ms;
for (int i = 0; i < M; ++i)if(d[U[i]]<1e9)ms.emplace(U[i],V[i]);
for(int i=1;i<N;++i)if(d[i]<1e9)ms.erase(ms.find({pare[i],i})),ms.erase(ms.find({i,pare[i]}));
for(auto[u,v]:ms){
int a=lca(u,v);
++cyclike[a];
}
int cc=0;
auto dfs=[&](auto&&dfs,int u)->int{
if(cyclike[u]){return 1;}
int z=0;
for(auto v:T[u])z|=dfs(dfs,v);
return z;
};
for(int v:g[0])cc+=dfs(dfs,v);
if(cyclike[0]) return true;
dfs(dfs,0);
if(cc<2)return false;
return false;
}
}
