#include "islands.h"
#include <variant>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
// <|°_°|>
// JeanBombeur & M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int MAX_ISLANDS = (1e5);
vector <pair <int, int>> Adj[MAX_ISLANDS];
vector <int> Up[MAX_ISLANDS];
int nbIslands, nbCanoes;
vector <int> Path[3];
vector <int> Cycle[2];
vector <int> Ans;
int Seen[MAX_ISLANDS];
int Deg[MAX_ISLANDS];
int Queue[MAX_ISLANDS];
int deb = 0, fin = 0;
int Dfs(int node, int id, int root) {
if (Seen[node])
return node;
Seen[node] = 1;
for (pair <int, int> dest : Adj[node])
{
if (Seen[dest.first] >= 0)
{
Path[id].push_back(dest.second);
int up = Dfs(dest.first, id, root);
if (!id)
{
if (up >= 0)
{
Cycle[id].push_back(dest.second);
Seen[node] = 2;
Path[id].pop_back();
}
else
Seen[node] = 0;
if (node != root)
return up == node ? -1 : up;
}
if (up >= 0 && Seen[up] == 1)
{
Path[id].pop_back();
Cycle[id].push_back(dest.second);
if (node != root)
return up == node ? -1 : up;
}
if (node != root || id)
return up;
id ++;
}
}
return -1;
}
void Add(vector <int> &a, int rev = 0) {
if (rev)
for (vector <int>::reverse_iterator it = a.rbegin(); it != a.rend(); it ++)
Ans.push_back(*it);
else
for (vector <int>::iterator it = a.begin(); it != a.end(); it ++)
Ans.push_back(*it);
return;
}
int Clear() {
for (int i = 0; i < nbIslands; i ++)
{
if (!Deg[i])
Queue[fin ++] = i;
}
int start = 0;
while (deb < fin || Deg[start] <= 1)
{
if (deb < fin)
{
int node = Queue[deb ++];
Seen[node] = -1;
for (int dest : Up[node])
if (!(-- Deg[dest]))
Queue[fin ++] = dest;
}
while (Deg[start] <= 1)
{
pair <int, int> next = {-1, 0};
Seen[start] = -1;
Deg[start] = 0;
for (int dest : Up[start])
if (!(-- Deg[dest]))
Queue[fin ++] = dest;
for (pair <int, int> dest : Adj[start])
if (!Seen[dest.first])
next = dest;
if (~next.first)
start = next.first, Path[2].push_back(next.second);
else
return -1;
}
}
return start;
}
variant <bool, vector <int>> find_journey(int N, int M, vector <int> Start, vector <int> End) {
nbIslands = N, nbCanoes = M;
for (int i = 0; i < nbCanoes; i ++)
{
Adj[Start[i]].push_back({End[i], i});
Deg[Start[i]] ++;
Up[End[i]].push_back(Start[i]);
}
int start = -1;
if ((start = Clear()) < 0)
return false;
Dfs(start, 0, start);
Add(Path[2]);
Add(Path[0]);
Add(Cycle[0], 1);
Add(Path[0], 1);
Add(Path[1]);
if (Cycle[1].empty())
{
int node = End[Path[1].back()];
int id = 0;
int sz = Cycle[0].size();
for (int i = 0; i < sz; i ++)
{
if (End[Cycle[0][i]] == node)
id = i;
}
for (int i = id; i < sz; i ++)
Ans.push_back(Cycle[0][i]);
for (int i = 0; i < id; i ++)
Ans.push_back(Cycle[0][i]);
}
else
Add(Cycle[1], 1);
Add(Path[1], 1);
if (!Cycle[1].empty())
{
Add(Path[0]);
Add(Cycle[0]);
Add(Path[0], 1);
Add(Path[1]);
Add(Cycle[1]);
Add(Path[1], 1);
}
Add(Path[2], 1);
return Ans;
}
