#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 1;
set<pair<int,int>> rev[M],nei[M];
bool del[M];
set<int> se;
int par[M], id[M], vis[M], r;
void rem()
{
int x=*se.begin();se.erase(x);
del[x]=1;
for (auto [i,j]:rev[x])
{
nei[i].erase({x,j});
if (nei[i].empty()) se.insert(i);
}
}
vector<int> cyc[2], pre[2];
void dfs(int u, int o)
{
vis[u]=1;
for (auto [i,x]:nei[u])
{
if (cyc[o].size()) return;
if (!vis[i])
par[i]=u, id[u]=x, dfs(i,o);
else if(vis[i]==1)
{
int v=u;
while (v!=i)
cyc[o].push_back(id[v]), v=par[v];
reverse(cyc[o].begin(), cyc[o].end());
cyc[o].push_back(x);
v=i;
while (v!=r)
pre[o].push_back(id[v]), v=par[v];
reverse(pre[o].begin(),pre[o].end());
}
}
vis[u]=2;
}
bool eq(vector<int> v, vector<int> v1)
{
sort(v.begin(), v.end());
sort(v1.begin(), v1.end());
return v==v1;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V)
{
for (int i=0;i<m;i++)
rev[V[i]].insert({U[i],i}),nei[U[i]].insert({V[i],i});
for (int i=0;i<n;i++)
if (nei[i].empty()) se.insert(i);
vector<int> v,ans;
int cur=0;
while (1)
{
while (!se.empty())
rem();
if (del[cur] && nei[cur].empty())
return false;
if (nei[cur].size()==1)
v.push_back(nei[cur].begin()->second), cur=nei[cur].begin()->first,
se.insert(cur),rem();
if (se.empty()) break;
}
vis[cur]=1, r=cur;
for (auto [i,x]:nei[cur])
par[i]=cur, id[i]=x;
auto it=nei[cur].begin();
dfs(it->first,0);it++;
dfs(it->first,1);
ans=v;
if (eq(cyc[0], cyc[1]))
{
for (int i:pre[0]) ans.push_back(i);
for (int i:cyc[0]) ans.push_back(i);
reverse(pre[0].begin(), pre[0].end());
for (int i:pre[0]) ans.push_back(i);
for (int i:pre[1]) ans.push_back(i);
reverse(cyc[1].begin(), cyc[1].end());
for (int i:cyc[1]) ans.push_back(i);
reverse(pre[1].begin(), pre[1].end());
for (int i:pre[1]) ans.push_back(i);
}
else
{
for (int i:pre[0]) ans.push_back(i);
for (int i:cyc[0]) ans.push_back(i);
reverse(pre[0].begin(), pre[0].end());
for (int i:pre[0]) ans.push_back(i);
for (int i:pre[1]) ans.push_back(i);
for (int i:cyc[1]) ans.push_back(i);
reverse(pre[1].begin(), pre[1].end());
for (int i:pre[1]) ans.push_back(i);
reverse(pre[0].begin(), pre[0].end());
for (int i:pre[0]) ans.push_back(i);
reverse(cyc[0].begin(), cyc[0].end());
for (int i:cyc[0]) ans.push_back(i);
reverse(pre[0].begin(), pre[0].end());
for (int i:pre[0]) ans.push_back(i);
reverse(pre[1].begin(), pre[1].end());
for (int i:pre[1]) ans.push_back(i);
reverse(cyc[1].begin(), cyc[1].end());
for (int i:cyc[1]) ans.push_back(i);
reverse(pre[1].begin(), pre[1].end());
for (int i:pre[1]) ans.push_back(i);
}
reverse(v.begin(), v.end());
for (int i:v) ans.push_back(i);
return ans;
}
