#include "islands.h"
#include <map>
#include <variant>
#include <vector>
#include <algorithm>
#include <iostream>
bool debug=0;
#define derr if(debug)cerr
using namespace std;
#define pb push_back
#define mp make_pair
// below are used to find the trip itself (path in terms of nodes)
vector<vector<int>> adj(1000);
vector<bool> visitted(1000, 0), been(1000, 0);
vector<int> goes(1000, -1), from(1000, -1);
int cycle_found=0;
// below are used to find the canoes to do the trip (path in terms of canoes)
vector<vector<int>> adjA(1000, vector<int>(1000, -1));
vector<vector<int>> adjB(1000, vector<int>(1000, -1));
void dfs(int node){
if(cycle_found)return;
been[node]=1;
visitted[node]=1;
for(int i=0; i<adj[node].size(); i++){
if(!been[adj[node][i]]){
// un-explored node...
goes[node] = adj[node][i];
from[adj[node][i]] = node;
dfs(adj[node][i]);
} else if(been[adj[node][i]] && visitted[adj[node][i]]){
// cycle found!!!
cycle_found = node+1;
goes[node] = adj[node][i];
from[adj[node][i]] = node;
return;
}
// otherwise, we have
// been[]=1 && visitted[]=0
// which means we've exhausted all options with this node already.
}
visitted[node]=0;
return;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
/*
adj[u] = {..., v, ...}
adjA[u][v] = first canoe for u->v
adjB[u][v] = second canoe for u->v
( trip[i] = {node to travel to, 0(A)/1(B)/2(reverse,A)/3(reverse,B)}
*/
int u,v;
for(int i=0; i<M; i++){
u=U[i]; v=V[i];
if(adjA[u][v] == -1){
adj[u].pb(v);
adjA[u][v] = i;
} else{
adjB[u][v] = i;
}
}
dfs(0);
if(cycle_found){
// now to find the canoes... (easy part? right? right???)
vector<int> answer;
// 0 -> cycle_found
int cur=0;
while(cur != cycle_found){
answer.pb(adjA[cur][goes[cur]]);
cur = goes[cur];
}
// cycle_found -> cycle_found (forwards) x2
answer.pb(adjA[cur][goes[cur]]);
cur = goes[cur];
while(cur != cycle_found){
answer.pb(adjA[cur][goes[cur]]);
cur = goes[cur];
}
answer.pb(adjB[cur][goes[cur]]);
cur = goes[cur];
while(cur != cycle_found){
answer.pb(adjB[cur][goes[cur]]);
cur = goes[cur];
}
// cycle_found <- cycle_found (backwards) x2
answer.pb(adjA[from[cur]][cur]);
cur = from[cur];
while(cur != cycle_found){
answer.pb(adjA[from[cur]][cur]);
cur = from[cur];
}
answer.pb(adjB[from[cur]][cur]);
cur = from[cur];
while(cur != cycle_found){
answer.pb(adjB[from[cur]][cur]);
cur = from[cur];
}
// 0 <- cycle_found (backwards)
while(cur != 0){
answer.pb(adjA[from[cur]][cur]);
cur = from[cur];
}
return answer;
}
else return false;
}
