#pragma once
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define MX 200000
bool dead[MX]{};
multiset<pair<int,int>> adj[MX];
vector<pair<int,int>> rev[MX];
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
//we should delete dead ends! just bc its fun!
for (int i = 0; i < M; i++) {
adj[U[i]].insert({ V[i], i });
rev[V[i]].push_back({ U[i], i });
}
vector<int> del;
for (int i = 0; i < N; i++) {
if (!adj[i].size()) del.push_back(i);
}
auto machine = [&]() {
while (del.size()) {
int i = del.back(); del.pop_back();
if (dead[i]) continue;
dead[i] = 1;
for (auto& x : rev[i]) {
adj[x.first].erase({ i, x.second });
if (!adj[x.first].size()) del.push_back(x.first);
}
}
};
machine();
int i = 0;
vector<int> initial_path;
while (1) {
if (dead[i]) return false;
if (adj[i].size() >= 2) break;
int t = i;
initial_path.push_back(adj[i].begin()->second);
i = adj[i].begin()->first;
del.push_back(t);
machine();
}
//35%
auto [a, pa] = *adj[i].begin();
auto [b, pb] = *adj[i].rbegin();
//find the loops of a and b
bool vis[MX] = {}; vis[i] = 1;
vector<int> la = {pa};
while (!vis[a]) {
vis[a] = 1;
la.push_back(adj[a].begin()->second);
a = adj[a].begin()->first;
}
auto lpa = la.begin();
if (a != i) lpa = find(la.begin(), la.end(), adj[a].begin()->second);
//document a's cycle
bool visa[MX] = {};
while (!visa[a]) {
visa[a] = 1;
a = adj[a].begin()->first;
}
bool vis2[MX] = {}; vis2[i] = 1;
vector<int> lb = { pb };
while (!visa[b] && !vis2[b]) {
vis2[b] = 1;
lb.push_back(adj[b].begin()->second);
b = adj[b].begin()->first;
}
auto lpb = lb.begin();
if (visa[b]) lpb = find(la.begin(), la.end(), adj[b].begin()->second);
else if (b != i) lpb = find(lb.begin(), lb.end(), adj[b].begin()->second);
// build the answer
std::vector<int>::iterator owo;
vector<int> ans;
ans.insert(ans.end(), initial_path.begin(), initial_path.end());
if (visa[b]) {
//case 1: same loop
//loop a
ans.insert(ans.end(), la.begin(), la.end());
vector<int> t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lb.end());
t = { lpb, la.end() };
t.insert(t.end(), lpa, lpb);
ans.insert(ans.end(), t.rbegin(), t.rend());
ans.insert(ans.end(), lb.rbegin(), lb.rend());
}
else {
//case 2: diff loop
//loop a
ans.insert(ans.end(), la.begin(), la.end());
vector<int> t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lb.end());
t = { lb.begin(), lpb };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop a
ans.insert(ans.end(), la.begin(), lpa);
t = { lpa, la.end() };
ans.insert(ans.end(), t.rbegin(), t.rend());
t = { la.begin(), lpa };
ans.insert(ans.end(), t.rbegin(), t.rend());
//loop b
ans.insert(ans.end(), lb.begin(), lpb);
t = { lpb, lb.end() };
ans.insert(ans.end(), t.rbegin(), t.rend());
t = { lb.begin(), lpb };
ans.insert(ans.end(), t.rbegin(), t.rend());
}
ans.insert(ans.end(), initial_path.rbegin(), initial_path.rend());
return ans;
}
//int main() {
// auto x = find_journey(2, 3, { 0, 0, 1}, { 1, 1, 0 });
// for (auto& i : get<vector<int>>(x)) cout << i << endl;
//}
