#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
const int N = 2e5;
vector<int> ans,to[N],canoe[N],prev_all;
deque<pair<int,int>> cycle,prev_cycle;
bitset<N> vu,vu3,path,prev_path,vu2;
bool impo = false, first_cycle = false;
int op1 = 0, op2 = 0, except = 0;
bool dfs2(int node){
if (path[node]){
op2 = node;
return true;
}
if (vu[node]) return false;
vu[node] = true;
path[node] = true;
for (int i=0; i<to[node].size(); ++i){
if (!vu3[canoe[node][i]] and (prev_path[canoe[node][i]] or dfs2(to[node][i]))){
if (prev_path[canoe[node][i]]){
op2 = canoe[node][i];
first_cycle = true;
}
else cycle.emplace_back(canoe[node][i],node);
return true;
}
}
path[node] = false;
return false;
}
bool dfs(int node){
// cout << node << endl;
if (path[node]){
op1 = node;
return true;
}
if (vu[node]) return false;
vu[node] = true;
path[node] = true;
for (int i=0; i<to[node].size(); ++i){
if (!vu3[canoe[node][i]] and dfs(to[node][i])){
cycle.emplace_back(canoe[node][i],node);
return true;
}
}
path[node] = false;
return false;
}
void construct(int deb){
// cout << deb << ' ' << to[deb].size() << endl;
if (vu2[deb]){
impo = true;
return;
}
except = deb;
vu2[deb] = true;
if (to[deb].empty()){
impo = true;
return;
}
else if (to[deb].size() == 1){
vu3[canoe[deb][0]] = true;
ans.emplace_back(canoe[deb][0]);
construct(to[deb][0]);
ans.emplace_back(canoe[deb][0]);
}
else{
int deja_vu = -1;
bool a = false, b = false;
for (int j=0; j<2*to[deb].size(); ++j){
int i = j%to[deb].size();
if (!a){
if (dfs(to[deb][i])){
vu.reset();
path.reset();
vector<int> extra;
prev_all.emplace_back(canoe[deb][i]);
ans.emplace_back(canoe[deb][i]);
// for (auto i:cycle) cout << i.first << ' ';
// cout << endl;
while (!cycle.empty() and op1 != cycle.back().second){
extra.emplace_back(cycle.back().first);
cycle.pop_back();
}
prev_cycle = cycle;
for (int node:extra) ans.emplace_back(node);
prev_all = extra;
for (auto node:cycle) prev_all.emplace_back(node.first);
reverse(cycle.begin(),cycle.end());
for (auto node:cycle){
prev_path[node.first] = true;
ans.emplace_back(node.first);
}
reverse(extra.begin(),extra.end());
for (int node:extra){
prev_all.emplace_back(node);
ans.emplace_back(node);
}
prev_all.emplace_back(canoe[deb][i]);
ans.emplace_back(canoe[deb][i]);
cycle.clear();
deja_vu = i;
a = true;
}
}
else if (i != deja_vu){
if (dfs2(to[deb][i])){
b = true;
ans.emplace_back(canoe[deb][i]);
if (first_cycle){
reverse(cycle.begin(),cycle.end());
for (auto i:cycle) ans.emplace_back(i.first);
reverse(cycle.begin(),cycle.end());
// cout << op2 << endl;
while (prev_cycle[0].first != op2){
prev_cycle.emplace_back(prev_cycle.front());
prev_cycle.pop_front();
}
prev_cycle.emplace_back(prev_cycle.front());
prev_cycle.pop_front();
for (auto i:prev_cycle) ans.emplace_back(i.first);
for (auto i:cycle) ans.emplace_back(i.first);
}
else{
vector<int> extra;
while (!cycle.empty() and op2 != cycle.back().second){
extra.emplace_back(cycle.back().first);
cycle.pop_back();
}
for (int node:extra) ans.emplace_back(node);
reverse(cycle.begin(),cycle.end());
for (auto i:cycle) ans.emplace_back(i.first);
reverse(extra.begin(),extra.end());
for (int node:extra) ans.emplace_back(node);
ans.emplace_back(canoe[deb][i]);
for (auto node:prev_all) ans.emplace_back(node);
ans.emplace_back(canoe[deb][i]);
reverse(extra.begin(),extra.end());
for (int node:extra) ans.emplace_back(node);
reverse(cycle.begin(),cycle.end());
for (auto node:cycle) ans.emplace_back(node.first);
reverse(extra.begin(),extra.end());
for (int node:extra) ans.emplace_back(node);
}
ans.emplace_back(canoe[deb][i]);
break;
}
}
}
if (!b) impo = true;
}
}
variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
for (int i=0; i<M; ++i){
// cout << U[i] << ' ' << V[i] << endl;
to[U[i]].emplace_back(V[i]);
canoe[U[i]].emplace_back(i);
}
construct(0);
if (impo) return false;
return ans;
}
