#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int MAXM = 250001;
int N;
vector<pair<int,int>> haha[MAXN];
vector<bool> bruh(MAXM);
vector<bool> troll(MAXN,true);
vector<int> dep(MAXN);
vector<pair<int,int>> edge(0);
vector<int> ped(MAXN);
vector<int> ted(0);
vector<int> ans(0);
vector<pair<int,int>> hbr(MAXN,{INT_MAX,0});
vector<bool> bro(MAXM,true);
void dfs(int a, int d) {
troll[a] = false;
dep[a] = d;
for(pair<int,int> v: haha[a]) {
if(troll[v.first]) {
bruh[v.second] = true;
dfs(v.first,d+1);
ped[v.first] = v.second;
}
}
}
vector<int> dude(int x, vector<pair<int,int>> idk) {
int n = N;
vector<bool> yo(N,true);
vector<int> wow(0);
for(int i = 1; i < idk.size()-1; i+=2) {
int c = edge[idk[i].second].first;
if(c == x) {
c = edge[idk[i].second].second;
}
yo[c] = false;
}
yo[x] = false;
for(int i = 1; i < n; i++) {
if(yo[i]) {
wow.push_back(ped[i]);
}
}
return wow;
}
int calc(int x, vector<pair<int,int>> wut) {
if(wut.size() == 1) {
return wut[0].second;
}
vector<int> yo1 = dude(x,wut);
vector<int> yo2 = dude(x,wut);
vector<pair<int,int>> wut1(0);
vector<pair<int,int>> wut2(0);
for(int i = 0; i < wut.size(); i++) {
if(i%2 == 0) {
yo1.push_back(wut[i].second);
wut1.push_back(wut[i]);
}
else {
yo2.push_back(wut[i].second);
wut2.push_back(wut[i]);
}
}
if(wut.size()%2 == 1) {
yo2.push_back(wut[wut.size()-1].second);
wut2.push_back(wut[wut.size()-1]);
}
if(count_common_roads(yo1) > count_common_roads(yo2)) {
return calc(x,wut1);
}
else {
return calc(x,wut2);
}
}
void apple(int a, int t) {
int n = N;
for(pair<int,int> v: haha[a]) {
if(bruh[v.second] && v.first != t) {
apple(v.first,a);
hbr[a] = min(hbr[a],hbr[v.first]);
}
}
vector<pair<int,int>> wut(0);
while(true) {
wut.clear();
for(pair<int,int> v: haha[a]) {
if(dep[v.first] < dep[a] && bro[v.second]) {
wut.push_back({dep[v.first],v.second});
}
}
if(wut.size() == 0) {
break;
}
sort(wut.begin(),wut.end());
reverse(wut.begin(),wut.end());
int w = calc(a,wut);
if(hbr[a].first < dep[a]) {
vector<int> wow(0);
for(int i = 1; i < n; i++) {
if(i != a) {
wow.push_back(ped[i]);
}
}
vector<int> wow2 = wow;
wow.push_back(hbr[a].second);
wow2.push_back(w);
if(count_common_roads(wow) > count_common_roads(wow2)) {
break;
}
}
hbr[a] = min(hbr[a],{min(dep[edge[w].first],dep[edge[w].second]),w});
bro[w] = false;
ans.push_back(w);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
int m = u.size();
for(int i = 0; i < m; i++) {
haha[u[i]].push_back({v[i],i});
haha[v[i]].push_back({u[i],i});
edge.push_back({u[i],v[i]});
}
dfs(0,0);
apple(0,-1);
return ans;
}
