#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
set <pair <int,int> > in[100010],out[100010];
vector <pair <int,int> > g[100010];
map <pair <int,int>,int> mp;
void reduce(){
queue <int> q;
for (int i=0; i<n; i++){
if (out[i].empty()) q.push(i);
}
while (!q.empty()){
int tp=q.front(); q.pop();
for (auto i:in[tp]){
out[i.first].erase({tp,i.second});
if (out[i.first].empty()) q.push(i.first);
}
in[tp].clear();
}
}
vector <int> prep;
int fol(int st){
set <int> seen;
seen.insert(st);
while (out[st].size()==1){
for (auto i:in[st]) out[i.first].erase({st,i.second});
in[st].clear();
prep.push_back((*out[st].begin()).second);
st=(*out[st].begin()).first;
if (seen.find(st)!=seen.end()) return -1;
}
if (out[st].empty()) return -1;
return st;
}
int visited[100010];
vector <int> vec;
bool found;
void dfs(int cur){
visited[cur]=1;
vec.push_back(cur);
for (auto i:g[cur]){
if (visited[i.first]==2) continue;
if (!visited[i.first]){
dfs(i.first);
if (found) return;
continue;
}
found=1;
vec.push_back(i.first);
}
if (found) return;
visited[cur]=2;
vec.pop_back();
}
void find_cycle(int st){
for (int i=0; i<n; i++) visited[i]=0;
vec.clear(); found=0;
dfs(st);
}
pair <vector <int>,vector <int> > getroute(){
int idx;
for (int i=0; i+1<vec.size(); i++) if (vec[i]==vec.back()){
idx=i;
break;
}
vector <int> path,cyc;
for (int i=1; i<=idx; i++) path.push_back(mp[{vec[i-1],vec[i]}]);
for (int i=idx+1; i<vec.size(); i++) cyc.push_back(mp[{vec[i-1],vec[i]}]);
return {path,cyc};
}
bool intrs(vector <int> a,vector <int> b){
set <int> sa;
for (int i:a) sa.insert(i);
for (int i:b) if (sa.find(i)!=sa.end()) return 1;
return 0;
}
vector <int> ans;
void append(vector <int> v,bool rev){
if (rev) reverse(v.begin(),v.end());
for (int i:v) ans.push_back(i);
}
variant <bool,vector <int> > find_journey(int N,int M,vector <int> U,vector <int> V){
n=N; m=M;
for (int i=0; i<M; i++){
out[U[i]].insert({V[i],i});
in[V[i]].insert({U[i],i});
}
reduce();
if (!out[0].size()) return false;
int st=0;
st=fol(st);
if (st==-1) return false;
for (int i:prep){
out[U[i]].erase({V[i],i});
in[V[i]].erase({U[i],i});
}
reduce();
if (!out[st].size()) return false;
for (int i=0; i<n; i++){
while (out[i].size()>1+(i==st)) out[i].erase(--out[i].end());
}
for (int i=0; i<n; i++){
for (auto j:out[i]){
g[i].push_back(j);
mp[{i,j.first}]=j.second;
}
}
find_cycle(st);
pair <vector <int>,vector <int> > p1=getroute();
bool W=0;
if (!p1.first.empty()) p1.first[0]=g[st][0].second;
else if (p1.second[0]!=g[st][0].second) W=1;
reverse(g[st].begin(),g[st].end());
find_cycle(st);
pair <vector <int>,vector <int> > p2=getroute();
append(prep,0);
if (W){
append(p1.second,0);
ans.push_back(g[st][1].second);
reverse(p1.second.begin(),p1.second.end());
p1.second.insert(p1.second.begin(),p1.second.back());
p1.second.pop_back();
append(p1.second,0);
ans.push_back(g[st][1].second);
} else if (intrs(p1.second,p2.second)){
append(p1.first,0);
append(p1.second,0);
append(p1.first,1);
append(p2.first,0);
append(p2.second,1);
append(p2.first,1);
} else {
append(p1.first,0);
append(p1.second,0);
append(p1.first,1);
append(p2.first,0);
append(p2.second,0);
append(p2.first,1);
append(p1.first,0);
append(p1.second,1);
append(p1.first,1);
append(p2.first,0);
append(p2.second,1);
append(p2.first,1);
}
append(prep,1);
return ans;
}
