#include <bits/stdc++.h>
#include <variant>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
vector<int > construct_journey(
vector<list<pair<int, int>>> nodes, int fork,
list<pair<int, int>>c2, list<pair<int, int>>c1_fork_to_cycle_pairs, list<pair<int, int>>c1_cycle_pairs, bool two_cycles) {
vector<int> journey;
if (two_cycles) {
list<int> start_to_fork, c1_fork_to_cycle, c1_cycle, c2_fork_to_cycle, c2_cycle;
// component2
int begin_cycle_c2 = c2.back().first;
c2_cycle.push_front(c2.back().second);
c2.pop_back();
while (c2.back().first != begin_cycle_c2) {
c2_cycle.push_front(c2.back().second);
c2.pop_back();
}
while (c2.back().first != fork) {
c2_fork_to_cycle.push_front(c2.back().second);
c2.pop_back();
}
while (!c2.empty()) {
start_to_fork.push_front(c2.back().second);
c2.pop_back();
}
start_to_fork.pop_front();
// component1
for (auto& i : c1_fork_to_cycle_pairs) {
c1_fork_to_cycle.push_back(i.second);
}
for (auto& i : c1_cycle_pairs) {
c1_cycle.push_back(i.second);
}
journey.reserve(2 * start_to_fork.size() + 4 * c1_fork_to_cycle.size() + 2 * c1_cycle.size() + 4 * c2_fork_to_cycle.size() + 2 * c2_cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
copy(c1_cycle.cbegin(), c1_cycle.cend(), back_inserter(journey));
copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
copy(c2_cycle.cbegin(), c2_cycle.cend(), back_inserter(journey));
copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
copy(c1_cycle.crbegin(), c1_cycle.crend(), back_inserter(journey));
copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
copy(c2_cycle.crbegin(), c2_cycle.crend(), back_inserter(journey));
copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
else {
list<int> start_to_fork, fork_to_join1, fork_to_join2, cycle;
// component2
while (c2.front().first != fork) {
start_to_fork.push_back(c2.front().second);
c2.pop_front();
}
start_to_fork.push_back(c2.front().second);
start_to_fork.pop_front();
c2.pop_front();
for (auto& i : c2) {
fork_to_join2.push_back(i.second);
}
for (auto& i : c1_cycle_pairs) {
cycle.push_back(i.second);
}
int join = c2.back().first;
// component1
auto it = c1_fork_to_cycle_pairs.cbegin();
while (it != c1_fork_to_cycle_pairs.cend() && (*it).first != join) {
fork_to_join1.push_back((*it++).second);
}
// join before the cycle
if (it != c1_fork_to_cycle_pairs.cend()) {
fork_to_join1.push_back((*it++).second);
list<int> join_to_cycle;
while (it != c1_fork_to_cycle_pairs.cend()) {
join_to_cycle.push_back((*it++).second);
}
journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 4 * join_to_cycle.size() + 2 * cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
// join inside the cycle
else {
journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 2 * cycle.size());
copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
// rotate the cycle
while (c1_cycle_pairs.back().first != join) {
c1_cycle_pairs.push_front(c1_cycle_pairs.back());
c1_cycle_pairs.pop_back();
cycle.push_front(cycle.back());
cycle.pop_back();
}
copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
}
}
return journey;
}
list<pair<int, int>> construct_cycle(vector<list<pair<int, int>>> nodes, int begin_cycle, vector<bool> unavailable_nodes) {
vector<bool> visited(nodes.size(), false);
vector<pair<int, int>> predecessors(nodes.size());
queue<int> bfs_queue;
visited[begin_cycle] = true;
bfs_queue.push(begin_cycle);
while (!bfs_queue.empty()) {
int last_node = bfs_queue.front();
bfs_queue.pop();
for (auto& next_edge : nodes[last_node]) {
if (!visited[next_edge.first] && !unavailable_nodes[next_edge.first]) {
visited[next_edge.first] = true;
bfs_queue.push(next_edge.first);
predecessors[next_edge.first] = make_pair(last_node, next_edge.second);
}
else if (next_edge.first == begin_cycle) {
list<pair<int, int>> cycle;
cycle.push_front(make_pair(next_edge.first, next_edge.second));
while (last_node != begin_cycle) {
cycle.push_front(make_pair(last_node, predecessors[last_node].second));
last_node = predecessors[last_node].first;
}
return cycle;
}
}
}
return {};
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
// pair out_node, out_edge
vector<list<pair<int, int>>> nodes(N);
for (auto i = 0; i < U.size(); i++) {
nodes[U[i]].push_back(make_pair(V[i], i));
}
vector<bool>
visited(nodes.size(), false),
in_path(nodes.size(), false),
begin_cycle(nodes.size(), false),
goal(nodes.size(), false);
stack<list<pair<int, int>>::const_iterator> dfs_stack;
list<pair<int, int>> path;
list<pair<int, int>> c1_fork_to_cycle, c1_cycle;
bool seek_component2 = false;
int fork = -1;
visited[0] = true;
in_path[0] = true;
dfs_stack.push(nodes[0].cbegin());
path.push_back(make_pair(0, -1));
while (!dfs_stack.empty()) {
int top_node = path.back().first;
goal[top_node] = seek_component2;
// first popped cycle -> found the cycle of component1
if (!seek_component2 && begin_cycle[top_node]) {
seek_component2 = true;
c1_cycle = construct_cycle(nodes, top_node, in_path);
visited = vector<bool>(nodes.size(), false);
for (auto& i : c1_cycle) {
visited[i.first] = true;
goal[i.first] = true;
}
for (auto& i : path) {
visited[i.first] = true;
}
}
// top_node has more successors
if (dfs_stack.top() != nodes[path.back().first].cend()) {
auto& [successor_node, successor_edge] = *dfs_stack.top();
dfs_stack.top()++;
// set new fork
if (seek_component2 && fork == -1) {
fork = top_node;
}
if (!visited[successor_node]) {
visited[successor_node] = true;
in_path[successor_node] = true;
dfs_stack.push(nodes[successor_node].cbegin());
path.push_back(make_pair(successor_node, successor_edge));
}
// found a cycle in component1
else if (!seek_component2 && in_path[successor_node]) {
begin_cycle[successor_node] = true;
}
// found component2
else if (goal[successor_node]) {
path.push_back(make_pair(successor_node, successor_edge));
// cycle found
if (in_path[successor_node]) {
return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, true);
}
// path to component1 found
else {
return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, false);
}
}
}
// top_node has no more successors -> pop it off the stack
else {
goal[top_node] = false;
if (top_node == fork) {
fork = -1;
}
if (seek_component2 && fork == -1) {
goal[top_node] = true;
c1_fork_to_cycle.push_front(path.back());
}
in_path[top_node] = false;
dfs_stack.pop();
path.pop_back();
}
}
return false;
}
