#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
int nr = 2 * m * (1 << m);
vector<vector<ii> > L(n);
for(int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
L[u].push_back({v, 2 * i});
L[v].push_back({u, 2 * i + 1});
}
auto get_vec = [&](int bm, int ultm, int u) -> vi {
vi Re;
for(auto [it, id] : L[u]) {
if(id / 2 != ultm && ((id & 1) == !!(bm & (1 << (id / 2))))) {
int b2 = bm ^ (1 << (id / 2));
Re.push_back(b2 * 2 * m + id);
}
}
return Re;
};
bool ok = false;
vi viz(nr, 0);
function<void(int)> dfs = [&](int id) {
int bm = id / (2 * m);
int ultm = id % (2 * m) / 2;
int u;
if(id & 1) u = U[ultm];
else u = V[ultm];
if(u == 0 && !bm) {
ok = 1;
//printf("!!!! Am vizitat nodul %d cu muchia %d (%d -> %d), bm=%d\n", u, ultm, U[ultm], V[ultm], bm);
return;
}
if(viz[id]) return;
viz[id] = 1;
// printf("Am vizitat nodul %d cu muchia %d (%d -> %d), bm=%d\n", u, ultm, U[ultm], V[ultm], bm);
auto Vec = get_vec(bm, ultm, u);
for(auto it : Vec) {
dfs(it);
}
};
for(auto [it, id]: L[0]) {
int bm = (1 << (id / 2));
dfs(bm * 2 * m + id);
}
return ok;
}
