#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(int i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (506)
vector<int> r, tmp;
int m, p[MAXN], state[MAXN*MAXN], depth[MAXN], pe[MAXN];
struct u {
int p[MAXN], sz[MAXN];
void init() {
FOR(i,0,MAXN-1) p[i]=i,sz[i]=1;
}
bool merge(int x,int y) {
x=find(x), y=find(y);
if(x==y) return 0;
if(sz[x]>sz[y]) swap(x, y);
p[x]=y, sz[y]+=sz[x]; return 1;
}
int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }
} u;
struct edge {
int x, ind;
}; vector<edge> v[MAXN];
bitset<MAXN*MAXN> span;
bitset<MAXN> vis;
int ask(vector<int> r) {
return count_common_roads(r);
}
vector<int> find_roads(int n, vector<int> U, vector<int> V) {
m = siz(U);
FOR(i,0,m-1) {
int a=U[i], b=V[i];
v[a].pb({b, i}), v[b].pb({a, i});
}
function<void(ll)>dfs=[&](ll x){
vis[x]=1;
for(auto i:v[x]) if(!vis[i.x]) {
depth[i.x]=depth[x]+1, p[i.x] = x, pe[i.x]=i.ind, dfs(i.x), span[i.ind] = 1, tmp.eb(i.ind);
}
};
dfs(0), assert(tmp.size() == n-1);
int init = ask(tmp);
FOR(i,0,m-1) if(!span[i]) {
int a=U[i], b=V[i];
if(depth[a] > depth[b]) swap(a, b);
vector<int> E;
int done = -1;
while(b ^ a) {
if(state[pe[b]]) done=pe[b];
else E.eb(pe[b]);
b = p[b];
}
if(E.empty()) continue;
if(done == -1) {
vector<pi> ind;
for(auto e:E) {
tmp.erase(find(all(tmp), e)), tmp.eb(i);
ind.eb(ask(tmp), e);
tmp.pop_back(), tmp.eb(e);
}
sort(all(ind));
if(ind[0].f == ind.back().f) {
for(auto i:ind) state[i.s] = init == i.f ? 1 : 2;
} else {
for(auto i:ind) if(i.f == ind.back().f) state[i.s] = 1; else state[i.s] = 2;
}
} else {
tmp.erase(find(all(tmp), done)), tmp.eb(i);
int init = ask(tmp);
tmp.pop_back(), tmp.eb(done);
for(auto e:E) {
tmp.erase(find(all(tmp), e)), tmp.eb(i);
if(ask(tmp) == init) state[e] = state[done];
else state[e] = 3 - state[done];
tmp.pop_back(), tmp.eb(e);
}
}
}
FOR(i,0,m-1) if(span[i] && state[i]==0) state[i] = 2; else if(!span[i]) assert(state[i] == 0);
// FOR(i,0,m-1) if(span[i]) {
// cerr<<i<<" is "<<state[i]<<'\n';
// }
FOR(i,0,n-1) {
deque<int> E;
for(auto j:v[i]) if(!span[j.ind] && !state[j.ind]) E.eb(j.ind);
if(E.empty()) continue;
shuffle(all(E), rng);
auto good=[&](ll until) {
vector<int> tmp2;
u.init();
FOR(ii,0,until) { int i=E[ii];
u.merge(U[i], V[i]);
tmp2.eb(i);
}
int cost = 0;
for(auto i:tmp) if(u.merge(U[i], V[i])) {
tmp2.eb(i), cost += state[i] == 2;
}
return ask(tmp2) - cost;
};
int have = good(siz(E) - 1);
for(;have;--have) {
assert(siz(E));
int st=-1, en=siz(E)-1;
while(en-st>1) {
int mid=(st+en)>>1;
if(good(mid)>=1) en=mid;
else st=mid;
}
FOR(j,0,en-1) state[E.front()]=1, E.pop_front();
state[E.front()]=2, E.pop_front();
}
while(E.size()) state[E.front()]=1, E.pop_front();
}
assert(r.empty());
FOR(i,0,m-1) if(state[i]==2) r.eb(i);
assert(siz(r)==n-1);
return r;
}
