#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
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<int> answer;
// subtask 3 (21 marks)
vector<vector<pair<int, int>>> ns(N);
// ns[node] = { {canoe1, nextIsland}, {canoe2, nextIsland}, {canoe3, nextIsland}, ...}
int u,v;
for(int i=0; i<M; i++){
u=U[i]; v=V[i];
ns[u].pb( mp(i,v) );
}
// simple case (same as subtask 2)
if(ns[0].size() == 0){
return false;
} else if(ns[0].size() > 1){
int a=ns[0][0].first;
int b;
if(a%2==0) b=a+1;
else b=a-1;
//int b = ((a%2==0) ? a+1 : a-1);
int c=ns[0][1].first;
int d;
if(c%2==0) d=c+1;
else d=c-1;
//int d = ((c%2==0) ? c+1 : c-1);
derr<<"simple case!\n";
answer = {a,b,c,d,b,a,d,c};
return answer;
}
// complex case
int prevc = ns[0][0].first;
vector<int> pretrip = {prevc};
prevc = (prevc%2 ? prevc-1 : prevc+1); // negate it so that prevc is the canoe that would take you right back...
int cur = ns[0][0].second;
vector<int> trip;
while(true){
derr<<"$ cur: "<<cur<<"\n";
if(ns[cur].size() == 1){
// there is only one canoe that started from this island
return false;
} else if(ns[cur].size() == 2){
derr<<"part of pretrip...\n";
// this island is merely part of the pretrip
if(ns[cur][0].first == prevc){
prevc = ns[cur][1].first;
cur = ns[cur][1].second;
} else{
prevc = ns[cur][0].first;
cur = ns[cur][0].second;
}
pretrip.pb(prevc);
derr<<"travelling with canoe "<<prevc<<". ";
prevc = (prevc%2 ? prevc-1 : prevc+1);
derr<<"now we should avoid canoe "<<prevc<<"!\n";
} else{
// trip located!
int a,b,c,d;
if(ns[cur][0].first == prevc){
a = ns[cur][1].first;
c = ns[cur][2].first;
} else if(ns[cur][1].first == prevc){
a = ns[cur][0].first;
c = ns[cur][2].first;
} else{
a = ns[cur][0].first;
c = ns[cur][1].first;
}
if(a%2==0) b = a+1;
else b = a-1;
if(c%2==0) d = c+1;
else d = c-1;
trip = {a,b,c,d,b,a,d,c};
for(int e:pretrip){
answer.pb(e);
}
for(int e:trip){
answer.pb(e);
}
for(int i=pretrip.size()-1; i>-1; i--){
answer.pb(pretrip[i]);
}
return answer;
}
}
}
