#include "islands.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
void validate(vi Sol, int n, int m, vi &U, vi &V) {
int u = 0;
vi stare(m, 0);
assert(!Sol.empty());
for(int i = 0; i + 1 < int(Sol.size()); ++i)
assert(Sol[i] != Sol[i + 1]);
for(auto it : Sol) {
if(!stare[it]) {
assert(u == U[it]);
} else {
assert(u == V[it]);
}
stare[it] ^= 1;
assert(u == U[it] || u == V[it]);
u = u ^ U[it] ^ V[it];
}
assert(u == 0);
for(int i = 0; i < m; ++i)
assert(!stare[i]);
}
vi solve(int n, int s, vector<ii> &b, vector<ii> &ToGo) {
ToGo[s] = b[0];
vector<ii> S;
vi viz(n, 0);
int v = s;
while(!viz[v]) {
viz[v] = 1;
auto [urm, id] = ToGo[v];
assert(urm != -1);
S.push_back(ToGo[v]);
v = urm;
}
vi apartine_c0(n, 0);
vi C0;
apartine_c0[v] = 1;
C0.push_back(S.back().second);
S.pop_back();
while(!S.empty() && S.back().first != v) {
apartine_c0[S.back().first] = 1;
C0.push_back(S.back().second);
S.pop_back();
}
reverse(C0.begin(), C0.end());
vi A0;
for(auto [v_other, id] : S) A0.push_back(id);
S.clear();
viz.assign(n, 0);
v = b[1].first;
S.push_back(b[1]);
while(!viz[v] && !apartine_c0[v]) {
viz[v] = 1;
auto [urm, id] = ToGo[v];
assert(urm != -1);
S.push_back(ToGo[v]);
v = urm;
}
if(apartine_c0[v]) {
///ai ajuns in c0
vi A1;
for(auto [v_other, id] : S) A1.push_back(id);
S.clear();
vi C1;
while(!viz[v]) {
viz[v] = 1;
auto [urm, id] = ToGo[v];
assert(urm != -1);
C1.push_back(id);
v = urm;
}
vi Sol;
copy(A0.begin(), A0.end(), back_inserter(Sol));
copy(C0.begin(), C0.end(), back_inserter(Sol));
copy(A0.rbegin(), A0.rend(), back_inserter(Sol));
copy(A1.begin(), A1.end(), back_inserter(Sol));
copy(C1.rbegin(), C1.rend(), back_inserter(Sol));
copy(A1.rbegin(), A1.rend(), back_inserter(Sol));
return Sol;
}
else {
///ai gasit un alt ciclu
vi C1;
C1.push_back(S.back().second);
S.pop_back();
while(!S.empty() && S.back().first != v) {
apartine_c0[S.back().first] = 1;
C1.push_back(S.back().second);
S.pop_back();
}
vi A1;
reverse(C1.begin(), C1.end());
for(auto [v_other, id] : S) A1.push_back(id);
S.clear();
vi Sol;
copy(A0.begin(), A0.end(), back_inserter(Sol));
copy(C0.begin(), C0.end(), back_inserter(Sol));
copy(A0.rbegin(), A0.rend(), back_inserter(Sol));
copy(A1.begin(), A1.end(), back_inserter(Sol));
copy(C1.begin(), C1.end(), back_inserter(Sol));
copy(A1.rbegin(), A1.rend(), back_inserter(Sol));
copy(A0.begin(), A0.end(), back_inserter(Sol));
copy(C0.rbegin(), C0.rend(), back_inserter(Sol));
copy(A0.rbegin(), A0.rend(), back_inserter(Sol));
copy(A1.begin(), A1.end(), back_inserter(Sol));
copy(C1.rbegin(), C1.rend(), back_inserter(Sol));
copy(A1.rbegin(), A1.rend(), back_inserter(Sol));
return Sol;
}
}
variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
vector<set<ii> > Smuchii(n), Smuchii2(n);
vector<bool> activ(n, true);
vi InDeg(n, 0), OutDeg(n, 0);
for(int i = 0; i < m; ++i) {
Smuchii[U[i]].insert({V[i], i});
Smuchii2[V[i]].insert({U[i], i});
++OutDeg[U[i]];
++InDeg[V[i]];
}
set<int> DeSters;
for(int i = 0; i < n; ++i) {
if((!InDeg[i] && i != 0) || !OutDeg[i]) {
DeSters.insert(i);
}
}
auto dezactiveaza = [&](int u) {
DeSters.erase(u);
activ[u] = false;
for(auto [it, id] : Smuchii[u]) {
--InDeg[it];
Smuchii2[it].erase({u, id});
if(!InDeg[it] && activ[it]) {
DeSters.insert(it);
}
}
for(auto [it, id] : Smuchii2[u]) {
--OutDeg[it];
Smuchii[it].erase({u, id});
if(!OutDeg[it] && activ[it]) {
DeSters.insert(it);
}
}
Smuchii[u].clear();
Smuchii2[u].clear();
OutDeg[u] = InDeg[u] = 0;
};
int s = 0;
while(!DeSters.empty()) {
int u = *DeSters.begin();
if(u == s && OutDeg[u]) {
DeSters.erase(u);
continue;
}
dezactiveaza(u);
}
if(!activ[0]) return false;
vi Start;
while(OutDeg[s] == 1) {
activ[s] = 0;
auto [ult, ultm] = *Smuchii[s].begin();
--OutDeg[s];
--InDeg[ult];
dezactiveaza(s);
s = ult;
if(!activ[s]) return false;
Start.push_back(ultm);
while(!DeSters.empty()) {
int u = *DeSters.begin();
if(u == s && OutDeg[u]) {
DeSters.erase(u);
continue;
}
dezactiveaza(u);
}
}
if(!activ[s] || OutDeg[s] < 2) return false;
vector<ii> ToGo(n, ii{-1, -1});
vector<ii> b;
for(int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
if(!activ[u] || !activ[v] || ToGo[u].second != -1)
continue;
if(u != s) {
ToGo[u] = {v, i};
} else {
b.push_back({v, i});
}
}
assert(b.size() == Smuchii[s].size());
auto Sol0 = solve(n, s, b, ToGo);
vi Sol;
copy(Start.begin(), Start.end(), back_inserter(Sol));
copy(Sol0.begin(), Sol0.end(), back_inserter(Sol));
copy(Start.rbegin(), Start.rend(), back_inserter(Sol));
// validate(Sol, n, m, U, V);
return Sol;
}
