#include "simurgh.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define here cerr<<"===============================\n"
#define pb push_back
#define fi first
#define sc second
#define si(a) (ll)(a.size())
using namespace std;
using ll = int;
using pll = pair<ll,ll>;
const ll maxn = 505;
ll n,m;
vector<ll> g[maxn];
array<ll,3> e[maxn];
ll in[maxn],ti = 0;
ll mn[maxn];
bool vis[maxn];
vector<ll> v;
ll tu[maxn];
ll par[maxn];
ll out[maxn];
bool intree(ll x,ll y){return in[x]<=in[y]&&out[x]>=out[y];}
void dfs(ll u,ll p) {
in[u] = ++ti;
vis[u] = 1;
mn[u] = in[u];
for(ll j : g[u]) {
ll s = e[j][0]^e[j][1]^u;
if(s==p) continue;
if(vis[s]) {
mn[u] = min(mn[u],mn[s]);
}else {
dfs(s,u);
mn[u] = min(mn[u],mn[s]);
v.pb(j);
par[s] = j;
if(mn[s]>=in[s]) tu[j] = 1;
}
}
out[u] = ti;
}
vector<ll> f(ll i,ll j) {
vector<ll> w;
for(ll x : v) if(x!=i) w.pb(x);
w.pb(j);
return w;
}
ll ask(vector<ll> v) {
vector<ll> w;
for(ll x : v) w.pb(x-1);
if(si(v)!=n-1) {
dbg(si(v));
cerr<<"losee"<<endl;
exit(0);
}
return count_common_roads(w);
}
vector<ll> cur;
ll dsu[maxn];
ll root(ll x) {
while(x!=dsu[x]) {
dsu[x] = dsu[dsu[x]];
x = dsu[x];
}
return x;
}
bool upd(ll x,ll y) {
x = root(x),y = root(y);
if(x==y) return 0;
dsu[x] = y;
return 1;
}
ll poc = 0;
void dodaj() {
iota(dsu+1,dsu+1+n,1);
for(ll i : cur) {
upd(e[i][0],e[i][1]);
}
poc = 0;
for(ll i : v) {
if(upd(e[i][0],e[i][1])) cur.pb(i),poc+=tu[i];
}
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> V) {
n = N;
m = si(u);
for(ll j = 0;j<m;j++) {
ll x = u[j]+1,y = V[j]+1;
g[x].pb(j+1);
g[y].pb(j+1);
e[j+1] = {x,y,j+1};
}
for(ll i = 1;i<=m;i++) tu[i] = -1;
dfs(1,1);
ll c = ask(v);
for(ll i : v) {
if(tu[i]==1||tu[i]==0) continue;
ll u = e[i][0],s = e[i][1];
if(in[u]>in[s]) swap(u,s);
ll k = -1;
for(ll j = 1;j<=m;j++) {
if(j==i) continue;
ll x = e[j][0],y = e[j][1];
if(in[x]>in[y]) swap(x,y);
if(!intree(x,y)) continue;
if(intree(x,u)&&intree(s,y)) {
k = j;
break;
}
}
ll x = e[k][0],y = e[k][1];
if(in[x]>in[y]) swap(x,y);
vector<ll> nw = f(i,k);
ll c2 = ask(nw);
vector<pll> tr;
tr.pb({c2,i});
bool imalos = 0;
ll mn = -1,mx = -1;
while(y!=x) {
ll j = par[y];
if(tu[j]!=-1) {
if(tu[j]==0) {
nw = f(j,k);
if(mx==-1) mx = ask(nw);
}else if(tu[j]==1) {
nw = f(j,k);
if(mn==-1) mn = ask(nw);
}
y = e[j][0]^e[j][1]^y;
continue;
}
nw = f(j,k);
tr.pb({ask(nw),j});
y = e[j][0]^e[j][1]^y;
}
sort(tr.begin(),tr.end());
if(mx!=-1) {
for(pll p : tr) {
if(p.fi==mx) tu[p.sc] = 0;
else tu[p.sc] = 1;
}
}else if(mn!=-1) {
for(pll p : tr) {
if(p.fi==mx) tu[p.sc] = 0;
else tu[p.sc] = 1;
}
}else {
mn = tr[0].fi,mx = tr.back().fi;
for(pll p : tr) {
if(p.fi==mx) tu[p.sc] = 0;
else tu[p.sc] = 1;
}
}
}
for(ll i = 1;i<=n;i++) {
cur.clear();
for(ll j : g[i]) cur.pb(j);
dodaj();
ll f = ask(cur)-poc;
ll last = 0;
for(ll j = 0;j<f;j++) {
ll tl = last,tr = si(g[i])-1,mid,rez = -1;
while(tl<=tr) {
mid = (tl+tr)/2;
cur.clear();
for(ll d = 0;d<=mid;d++) cur.pb(g[i][d]);
dodaj();
ll cnt = ask(cur)-poc;
if(cnt>j) rez = mid,tr = mid-1;
else tl = mid+1;
}
if(rez==-1) while(1) here;
tu[g[i][rez]] = 1;
last = rez+1;
}
}
vector<ll> ans;
for(ll i = 1;i<=m;i++) if(tu[i]==1) ans.pb(i-1);
//cerr<<si(ans)<<endl;
//cerr<<"ans: "<<endl;
//for(ll x : ans) cerr<<x<< " ";
//cerr<<endl;
return ans;
}
