#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
using pii = pair<int, int>;
vector<int> generate_cycle(int N, vector<vector<pii>> (&edges), int start)
{
//This function returns a cycle containing start, or reports that none exist
vector<int> parent(N, -2);
vector<int> parent_canoe(N, -2);
queue<int> visitlist;
parent[start] = -1;
visitlist.push(start);
while (!visitlist.empty())
{
int x = visitlist.front();
visitlist.pop();
for (pii neigh: edges[x])
{
int adj = neigh.first;
int can = neigh.second;
if (parent[adj]==-2)
{
parent[adj] = x;
parent_canoe[adj] = can;
visitlist.push(adj);
}
if (adj == start)
{
//create the cycle
int curr = x;
vector<int> cycle;
cycle.push_back(can);
while (curr!=start)
{
cycle.push_back(parent_canoe[curr]);
curr = parent[curr];
}
//this cycle is actually reversed, so let's reverse it!
int k = cycle.size();
vector<int> real_cycle(k);
for (int i=0; i<k; i++)
real_cycle[i] = cycle[k-1-i];
return real_cycle;
}
}
}
return {};
}
bool journey_exists = 0;
vector<int> journey(int N, vector<vector<pii>> (&edges), vector<bool> (&in_cycle))
{
vector<int> parent(N, -2);
vector<int> parent_canoe(N, -2);
queue<int> visitlist;
parent[0] = -1;
visitlist.push(0);
while (!visitlist.empty())
{
int x = visitlist.front();
visitlist.pop();
if (in_cycle[x])
{
vector<int> cycle = generate_cycle(N, edges, x);
int curr = x;
vector<int> pre;
while (curr!=0)
{
pre.push_back(parent_canoe[curr]);
curr = parent[curr];
}
int k = pre.size();
vector<int> real_pre(k);
for (int i=0; i<k; i++)
real_pre[i] = pre[k-1-i];
int kc = cycle.size();
vector<int> journey;
for (int i=0; i<k; i++)
journey.push_back(real_pre[i]);
for (int i=0; i<kc; i++)
journey.push_back(cycle[i]);
for (int i=0; i<kc; i++)
journey.push_back(cycle[i]+1);
for (int i=0; i<kc; i++)
journey.push_back(cycle[kc-i-1]);
for (int i=0; i<kc; i++)
journey.push_back(cycle[kc-i-1]+1);
for (int i=0; i<k; i++)
journey.push_back(pre[i]);
journey_exists = 1;
return journey;
}
for (pii neigh: edges[x])
{
int adj = neigh.first;
int can = neigh.second;
if (parent[adj]==-2)
{
parent[adj] = x;
parent_canoe[adj] = can;
visitlist.push(adj);
}
}
}
return {};
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
journey_exists = 0;
vector<vector<pii>> edges(N);
vector<int> out_deg(N, 0);
vector<int> in_deg(N, 0);
vector<vector<int>> edges_out(N);
vector<vector<int>> edges_in(N);
for (int i=0; i<M; i+=2)
{
int u = U[i];
int v = V[i];
edges[u].push_back({v, i});
out_deg[u]++;
in_deg[v]++;
edges_out[u].push_back(v);
edges_in[v].push_back(u);
}
//clear all nodes that don't have anything going into it
queue<int> work;
for (int i=0; i<N; i++)
if (in_deg[i] == 0)
work.push(i);
while (!work.empty())
{
int x = work.front();
work.pop();
for (int y: edges_out[x])
{
out_deg[x]--;
in_deg[y]--;
if (in_deg[y] == 0)
work.push(y);
}
}
//clear all nodes that don't have anything going out of it
for (int i=0; i<N; i++)
if (out_deg[i] == 0)
work.push(i);
while (!work.empty())
{
int x = work.front();
work.pop();
for (int y: edges_in[x])
{
in_deg[x]--;
out_deg[y]--;
if (out_deg[y] == 0)
work.push(y);
}
}
//cout << "nakarating po dito\n";
vector<bool> in_cycle(N, 0);
for (int i=0; i<N; i++)
if ((out_deg[i]>0) and (in_deg[i]>0))
in_cycle[i] = 1;
vector<int> sagot = journey(N, edges, in_cycle);
if (journey_exists == 0)
return journey_exists;
return sagot;
}
