#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int query(){
return count_common_roads(R);
}
vector<int>U,V;
set<int>subtree[501];
vector<int>AADJ[10010],adj[501];
int indexofr[501][501];
bitset<501>vis;
vector<int>origintree;
int N_,K_;
struct dsu{
int par[501];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
bool merge(int a,int b){
a=abp(a+1),b=abp(b+1);
if(a==b) return 0;
return par[a]=b;
}
void reset(){
memset(par,0,sizeof par);
}
} tis, TIS2;
void gendfstree(int n){
vis[n]=1;
subtree[n].insert(n);
for(auto i:AADJ[n]){
if(vis[i])continue;
gendfstree(i);
for(auto j:subtree[i])
subtree[n].insert(j);
adj[i].push_back(n);
adj[n].push_back(i);
origintree.push_back(indexofr[n][i]);
}
}
void mergethese(set<int>st){
tis.reset();
for(int i=0;i<U.size();i++){
int a=U[i],b=V[i];
if(!st.count(a)||!st.count(b))
continue;
if(tis.merge(a,b))
R.push_back(i);
}
tis.reset();
for(int i=0;i<U.size();i++){
int a=U[i],b=V[i];
if(st.count(a)||st.count(b))
continue;
if(tis.merge(a,b))
R.push_back(i);
}
}
void specialcheck(int n){
}
vector<int>ans;
void findstuff(int n,int p){
for(auto i:adj[n])
if(i-p)findstuff(i,n);
if(!n)return;
vector<int>R2=R;
R.clear();
mergethese(subtree[n]);
vector<int>specrod;
for(auto i:AADJ[n])
if(subtree[i].size()>subtree[n].size())
specrod.push_back(indexofr[i][n]);
map<int,vector<int>>mp;
for(auto i:specrod){
R.push_back(i);
mp[query()].push_back(i);
R.pop_back();
}
vector<int>C=prev(mp.end())->second;
int D=prev(mp.end())->first;
if(mp.size()==2){
for(auto i:C)
TIS2.merge(U[i],V[i]),
ans.push_back(i);
} else {
int cond=1;
if(subtree[n].size()==1)
cond=1;
else {
for(int i=0;i<U.size();i++){
int a=U[i],b=V[i];
if(a-n&&b-n&&subtree[n].count(a)!=subtree[n].count(b)){
R.push_back(i);
if(query()+!(count(ans.begin(),ans.end(),i))>D)
cond=0;
break;
}
}
}
if(cond) for(auto i:C)
TIS2.merge(U[i],V[i]),
ans.push_back(i);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
U=u;
V=v;
N_=n;
int m=u.size();
if(m==n-1){
ans.resize(m);
iota(ans.begin(),ans.end(),0);
return ans;
}
for(int i=0;i<m;i++)
AADJ[u[i]].push_back(v[i]),
AADJ[v[i]].push_back(u[i]),
indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i;
gendfstree(0);
findstuff(0,0);
return ans;
}
