#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define ln '\n'
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
map <vector<int>,int> dp;
int qry(vector <int> x){
sort(all(x));
if ( !dp.count(x) ){
dp[x] = count_common_roads(x);
}
return dp[x];
}
int ask(set <int> s){
vector <int> x;
for ( auto &u: s ) x.pb(u);
return qry(x);
}
vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V){
int m = U.size();
vector <vector<ar<int,2>>> adj(n);
for ( int i = 0; i < m; i++ ){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
vector <int> f(m, -1), d(n, -1), is(m);
vector <ar<int,2>> fa(n, {-1, -1}), b(n);
auto dfs = [&](auto dfs, int u, int p) -> void{
ar <int,2> back = {n + 1, -1};
for ( auto &[v, j]: adj[u] ){
if ( v != p ){
if ( d[v] == -1 ){
d[v] = d[u] + 1;
fa[v] = {u, j};
is[j] = 1;
dfs(dfs, v, u);
} else if ( d[v] < d[u] ){
if ( back[1] == -1 || d[back[0]] > d[v] ){
back = {v, j};
}
}
}
}
b[u] = back;
};
d[0] = 0;
dfs(dfs, 0, -1);
set <int> et;
for ( int i = 0; i < m; i++ ){
if ( is[i] ) et.insert(i);
}
int C = ask(et);
auto dfs2 = [&](auto dfs2, int u, int p) -> void{
for ( auto &[v, j]: adj[u] ){
if ( v != p && is[j] ){
dfs2(dfs2, v, u);
}
}
int j = fa[u][1];
if ( j == -1 ) return;
auto &bb = b[u];
if ( bb[1] == -1 ){
if ( f[j] == -1 ) f[j] = 1;
} else{
vector <int> p;
int v = u;
while ( v != bb[0] ){
p.pb(fa[v][1]);
v = fa[v][0];
}
sort(all(p), [&](int &u, int &v){
return f[u] > f[v];
});
vector <int> R;
int tmp = -1;
et.insert(bb[1]);
for ( auto &j: p ){
et.erase(j);
if ( f[j] != -1 ){
if ( tmp == -1 ){
tmp = ask(et);
if ( tmp == C ){
f[bb[1]] = f[j];
} else{
f[bb[1]] = (tmp > C);
assert(f[bb[1]] != f[j]);
}
}
} else{
int q = ask(et);
if ( q == C ){
R.pb(j); // f[j] == f[bb[1]]
} else{
f[bb[1]] = (q > C);
f[j] = f[bb[1]] ^ 1;
}
}
et.insert(j);
}
et.erase(bb[1]);
if ( f[bb[1]] == -1 ){
f[bb[1]] = 0;
}
for ( auto &x: R ) f[x] = f[bb[1]];
}
};
dfs2(dfs2, 0, -1);
for ( int root = 0; root < n; root++ ){
vector <int> fa(n);
auto dfs = [&](auto dfs, int u, int p) -> void{
for ( auto &[v, j]: adj[u] ){
if ( v != p && is[j] ){
fa[v] = j;
dfs(dfs, v, u);
}
}
};
dfs(dfs, root, -1);
vector <ar<int,2>> p;
for ( auto &[v, j]: adj[root] ){
if ( f[j] == -1 ) p.pb({fa[v], j});
}
int it = 0, k = p.size();
while ( it < k ){
int l = it, r = k;
auto ok = [&](int m){
int tmp = C;
for ( int j = it; j <= m; j++ ){
et.insert(p[j][1]);
et.erase(p[j][0]);
tmp -= f[p[j][0]];
}
int q = ask(et);
for ( int j = it; j <= m; j++ ){
et.erase(p[j][1]);
et.insert(p[j][0]);
}
return q != tmp;
};
while ( l < r ){
int m = (l + r) / 2;
if ( ok(m) ){
r = m;
} else l = m + 1;
}
for ( int j = it; j < l; j++ ){
f[p[j][1]] = 0;
}
if ( l < k ) f[p[l][1]] = 1;
it = l + 1;
}
}
for ( auto &x: f ){
assert(x != -1);
}
vector <int> ans;
for ( int i = 0; i < m; i++ ){
if ( f[i] ) ans.pb(i);
}
return ans;
}
