#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"
struct directed_graph{
ll N;
vii edge, revedge;
vi par;
vii V;
directed_graph(vii E){
N = E.size();
edge.resize(N);
revedge.resize(N);
par.resize(N);
V.resize(N);
rep(i,0,N){
for(auto j: E[i]){
edge[i].pb(j);
revedge[j].pb(i);
}
}
}
vi ord;
vector<bool> flag;
void dfs1(ll now){
flag[now] = true;
for(auto next: edge[now]){
if(flag[next]) continue;
dfs1(next);
}
ord.pb(now);
}
void dfs2(ll p, ll now){
flag[now] = true;
par[now] = p;
for(auto next: revedge[now]){
if(flag[next]) continue;
dfs2(p, next);
}
}
void SCC(){
flag.resize(N);
rep(i,0,N){
if(!flag[i]) dfs1(i);
}
reverse(all(ord));
flag.assign(N,false);
for(auto el: ord){
if(!flag[el]){
dfs2(el,el);
}
}
rep(i,0,N) V[par[i]].pb(i);
}
};
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
vii edge(N), index(N);
rep(i,0,M){
edge[U[i]].pb(V[i]);
index[U[i]].pb(i);
}
directed_graph G(edge);
G.SCC();
ll good = -1;
vi ans;
{
std::queue<ll> que;
que.push(0);
vi flag(N);
vi rev(N,-1);
vi idx(N);
flag[0] = true;
rev[0] = 0;
while(!que.empty()){
ll now = que.front(); que.pop();
if(G.V[G.par[now]].size() >= 2 && edge[now].size() >= 2){
good = now;
while(now != 0){
ans.pb(idx[now]);
now = rev[now];
}
reverse(all(ans));
break;
}
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(flag[next]) continue;
flag[next] = true;
rev[next] = now;
idx[next] = index[now][i];
que.push(next);
}
}
}
if(good != -1){
std::set<ll> used;
for(auto el: ans){
used.insert(el);
used.insert(el^1);
}
std::queue<ll> que;
que.push(good);
vi rev(N,-1);
vi idx(N);
rev[good] = good;
while(!que.empty()){
ll now = que.front(); que.pop();
rep(i,0,edge[now].size()){
ll next = edge[now][i];
if(rev[next] != -1) continue;
if(used.count(index[now][i])) continue;
rev[next] = now;
idx[next] = index[now][i];
que.push(next);
}
}
rep(i,0,N){
if(rev[i] != -1){
vi ans2;
rep(j,0,edge[i].size()){
if(used.count(index[i][j])) continue;
ll next = edge[i][j];
if(next == good){
ans2.pb(index[i][j]);
break;
}
}
if(ans2.empty()) continue;
ll now = i;
while(now != good){
ans2.pb(idx[now]);
now = rev[now];
}
ll len = ans.size();
reverse(all(ans2));
for(auto el: ans2) ans.pb(el);
for(auto el: ans2) ans.pb(el^1);
reverse(all(ans2));
for(auto el: ans2) ans.pb(el);
for(auto el: ans2) ans.pb(el^1);
per(i,len-1,0) ans.pb(ans[i]);
return ans;
}
}
}
return false;
}
