#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
int stopien_wyjscia[100010];
set<pair<int, int>>graf[100010], graf1[100010];
bool usuniete[100010];
vector<int>answer;
bool czy[100010];
bool odw1[100010];
vector<int>stos;
bool flaga_znaleziono = 0;
void dfs(int start){
czy[start] = 1;
odw1[start] = 1;
for(auto j: graf[start]){
if(czy[j.first]){
stos.push_back(j.second);
flaga_znaleziono = 1;
return;
}
if(!odw1[j.first]){
stos.push_back(j.second);
dfs(j.first);
if(flaga_znaleziono)return;
stos.pop_back();
}
}
czy[start] = 0;
}
variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U, std::vector<int> V) {
int i;
for(i=0;i<m;i++){
graf[U[i]].insert({V[i], i});
graf1[V[i]].insert({U[i], i});
stopien_wyjscia[U[i]]++;
//graf[V[i]].push_back({U[i], i+1});
}
int start = 0;
queue<int>kolejka;
for(i=0;i<n;i++)
if(stopien_wyjscia[i]==0)
kolejka.push(i);
vector<int>poczatek;
while(true){
// printf("%d\n", start);
// for(i=0;i<n;i++)printf("%d ", stopien_wyjscia[i]);printf("\n");
if(stopien_wyjscia[start]==0)return false;
if(stopien_wyjscia[start]==1){
for(auto j: graf1[start])
if(--stopien_wyjscia[j.first]==0)
kolejka.push(j.first);
usuniete[start] = 1;
for(auto j: graf[start])
if(!usuniete[j.first]){
start = j.first;
answer.push_back(j.second);
break;
}
continue;
}
if(!kolejka.size())break;
auto x = kolejka.front();
kolejka.pop();
if(usuniete[x])continue;
usuniete[x] = 1;
for(auto j: graf1[x])
if(--stopien_wyjscia[j.first]==0)
kolejka.push(j.first);
}
if(stopien_wyjscia[start]<=1)return false;
poczatek = answer;
for(i=0;i<n;i++){
vector<pair<int,int>>do_usu;
for(auto j: graf[i])
if(usuniete[j.first])do_usu.push_back(j);
for(auto j: do_usu)
graf[i].erase(j);
}
czy[start] = 1;
odw1[start] = 1;
stos.push_back((*graf[start].begin()).second);
dfs((*graf[start].begin()).first);
vector<int>pierwsza = stos;
stos.clear();
for(i=0;i<n;i++)odw1[i] = 0;
czy[start] = 1;
odw1[start] = 1;
stos.push_back((*graf[start].rbegin()).second);
if(!czy[(*graf[start].rbegin()).second])
dfs((*graf[start].rbegin()).second);
vector<int>druga = stos;
// for(auto j: pierwsza)printf("%d ", j);printf("\n");
// for(auto j: druga)printf("%d ", j);printf("\n");
for(i=0;i<n;i++)graf[i].clear();
for(auto j: pierwsza)
graf[U[j]].insert({V[j], j});
for(auto j: druga)
graf[U[j]].insert({V[j], j});
int x = start;
int policz = 0, pop = -1;
while(true){
// printf("%d, ", x);
if(x==start)policz++;
if(policz==13)break;
auto it = *graf[x].begin();
if(it.second==pop)
it = *graf[x].rbegin();
answer.push_back(it.second);
graf[x].erase(it);
graf[it.first].insert({x, it.second});
x = it.first;
pop = it.second;
}
while(poczatek.size()){
answer.push_back(poczatek.back());
poczatek.pop_back();
}
return answer;
}
