#include <bits/stdc++.h>
#include "simurgh.h"
#define pb push_back
using namespace std;
struct UFDS {
vector<int> e;
int operator()(int u) {
return e[u] < 0 ? u : e[u] = (*this)(e[u]);
}
bool operator()(int u, int v) {
if((u = (*this)(u)) == (v = (*this)(v))) return false;
if(e[u] > e[v]) swap(u, v);
e[u] += e[v], e[v] = u;
return true;
}
UFDS(int n) { e.assign(n, -1); }
};
const int Z = 500, NE = Z * Z / 2;
int vis[Z], visE[NE], t[NE], over[NE];
vector<int> st;
vector<array<int, 2>> g[Z], s, h[NE], q;
vector<array<int, 3>> o;
int ask(int u, int v) {
for(int &j : st) if(j == u) j = v;
int res = count_common_roads(st);
for(int &j : st) if(j == v) j = u;
return res;
}
void dfs(int u, int p) {
vis[u] = 1;
for(auto [v, i] : g[u]) if(v != p) {
if(vis[v] == 1) {
for(int j = size(s); j--; ) {
over[s[j][1]] = i;
t[s[j][1]] = -1;
if(s[j][0] == v) break;
if(!visE[s[j][1]]++) o.pb({s[j][1], s[j-1][1], i});
}
} else if(!vis[v]) {
s.pb({u, i});
st.pb(i);
t[i] = 1;
dfs(v, u);
s.pop_back();
}
}
vis[u] = 2;
}
void color(int u) {
for(auto [v, w] : h[u]) if(t[v] < 0) {
t[v] = t[u] ^ w;
color(v);
}
}
vector<int> find_roads(int n, vector<int> U, vector<int> V) {
for(int i = size(U); i--; ) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
fill(t, t + NE, -1);
dfs(0, 0);
int def = count_common_roads(st);
for(auto [a, b, i] : o) {
int x = ask(a, i), y = ask(b, i);
h[b].pb({a, x != y});
h[a].pb({b, x != y});
if(x != y) q.pb({a, x < y});
}
while(1) {
for(auto [u, w] : q) if(t[u] < 0) {
t[u] = w;
color(u);
}
q.clear();
bool done = 1;
for(int i : st) if(t[i] < 0) {
int e = over[i];
done = 0;
q.pb({i, ask(i, e) < def});
}
if(done) break;
}
for(int u = 0; u < n; ++u) {
vector<int> a;
for(auto [v, i] : g[u]) if(u < v && t[i] < 0)
a.pb(i);
while(!empty(a)) {
int x = 0;
for(int y = 1<<10; y /= 2; ) if(x + y <= (int)size(a)) {
x += y;
UFDS uf(n);
vector<int> qry;
for(int i = 0; i < x; ++i) {
uf(U[a[i]], V[a[i]]);
qry.pb(a[i]);
}
int cnt {};
for(int e : st) if(uf(U[e], V[e])) {
qry.pb(e);
cnt += t[e];
}
if(cnt < count_common_roads(qry)) x -= y;
}
for(int i = 0; i < x; ++i)
t[a[i]] = 0;
if(x == (int)size(a)) break;
t[a[x]] = 1;
a = vector<int> {begin(a) + x + 1, end(a)};
}
}
vector<int> res;
for(int i = size(U); i--; )
if(t[i] == 1) res.pb(i);
return res;
}
