#include "islands.h"
#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]);
}
variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
vector<set<int> > 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]);
Smuchii2[V[i]].insert(U[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);
}
}
while(!DeSters.empty()) {
int u = *DeSters.begin();
DeSters.erase(u);
activ[u] = false;
for(auto it : Smuchii[u]) {
--InDeg[it];
Smuchii2[it].erase(u);
if(!InDeg[it] && activ[it]) {
DeSters.insert(it);
}
}
for(auto it : Smuchii2[u]) {
--OutDeg[it];
Smuchii[it].erase(u);
if(!OutDeg[it] && activ[it]) {
DeSters.insert(it);
}
}
}
if(!activ[0]) return false;
///am curatat graful
vector<vector<ii> > L(n);
for(int i = 0; i < m; ++i) {
if(activ[U[i]] && activ[V[i]]) {
L[U[i]].push_back({V[i], i});;
}
}
vi S;
vi viz(n, 0);
vi Sol;
bool ok = false;
function<void(int, int)> dfs = [&](int u, int ultm) {
if(ok) return;
if(viz[u] == 2) return;
if(viz[u] == 1) {
vi Cyc;
Cyc.push_back(S.back());
S.pop_back();
while(!S.empty() && V[S.back()] != u) {
Cyc.push_back(S.back());
S.pop_back();
}
vi S1 = S;
for(auto it : S1) Sol.push_back(it);
reverse(Cyc.begin(), Cyc.end());
for(auto it : Cyc) Sol.push_back(it);
for(auto it : Cyc) Sol.push_back(it ^ 1);
reverse(Cyc.begin(), Cyc.end());
for(auto it : Cyc) Sol.push_back(it);
for(auto it : Cyc) Sol.push_back(it ^ 1);
reverse(S1.begin(), S1.end());
for(auto it : S1) Sol.push_back(it);
ok = 1;
return;
}
viz[u] = 1;
for(auto [it, id] : L[u]) {
if(id / 2 == ultm / 2) continue;
S.push_back(id);
dfs(it, id);
if(ok) break;
if(!S.empty() && S.back() == id) S.pop_back();
}
viz[u] = 2;
};
dfs(0, -2);
if(Sol.empty()) return false;
validate(Sol, n, m, U, V);
return Sol;
}
