#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(MAXN,-1);
vector<int> ans(0);
vector<pair<int,int>> hbr(MAXN,{INT_MAX,0});
vector<bool> bro(MAXM,true);
vector<bool> proc(MAXN,true);
int g;
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;
}
pair<int,bool> calc(int x, vector<pair<int,int>> wut) {
if(wut.size() == 1) {
return {wut[0].second,false};
}
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]);
}
int a = count_common_roads(yo1),b = count_common_roads(yo2);
pair<int,bool> u;
if(a > b) {
u = calc(x,wut1);
}
else {
u = calc(x,wut2);
}
if(u.second || a != b) {
return u;
}
int br = 0;
for(int v: yo1) {
if(u.first == v) {
br++;
}
}
for(int v: yo2) {
if(u.first == v) {
br++;
}
}
if(br == 2) {
return {u.first,false};
}
else {
return {u.first,true};
}
}
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]);
}
}
if(a == 0) {
return;
}
vector<pair<int,int>> wut(0);
if(hbr[a].first >= dep[a]) {
proc[a] = 0;
ted[a] = 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());
pair<int,bool> w1 = calc(a,wut);
int w = w1.first;
/*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);
if(w == ped[a]) {
ted[a] = 1;
}
if(!w1.second) {
break;
}
}
}
else {
vector<int> yo(0);
for(int i = 1; i < n; i++) {
if(i != a) {
yo.push_back(ped[i]);
}
}
yo.push_back(hbr[a].second);
if(count_common_roads(yo) == g) {
ted[a] = 1;
ans.push_back(ped[a]);
}
else {
ted[a] = 0;
}
}
}
int calc2(int x, vector<int> idk) {
int n = N;
vector<int> yo(0);
vector<bool> pear(n,true);
int sb = g;
pair<int,int> sm = {INT_MAX,-1};
pear[x] = false;
sb-=ted[x];
for(int v: idk) {
yo.push_back(v);
int c = edge[v].first;
if(c == x) {
c = edge[v].second;
}
pear[c] = false;
pair<int,int> sm2 = {dep[c],c};
sm = min(sm,sm2);
sb-=ted[c];
}
pear[sm.second] = true;
sb+=ted[sm.second];
for(int i = 1; i < n; i++) {
if(pear[i]) {
yo.push_back(ped[i]);
}
}
return count_common_roads(yo)-sb;
}
void piglin(int x, vector<int> idk, int br) {
if(br == 0 || idk.size() == 0) {
return;
}
if(idk.size() == 1) {
ans.push_back(idk[0]);
return;
}
int s = idk.size();
vector<int> a(0);
vector<int> b(0);
for(int i = 0; i < s/2; i++) {
a.push_back(idk[i]);
}
for(int i = s/2; i < s; i++) {
b.push_back(idk[i]);
}
int y = calc2(x,a);
piglin(x,a,y);
piglin(x,a,br-y);
}
void orange(int a, int t) {
int n = N;
for(pair<int,int> v: haha[a]) {
if(bruh[v.second] && v.first != t) {
orange(v.first,a);
}
}
if(a == 0) {
return;
}
vector<int> idk(0);
if(proc[a]) {
for(pair<int,int> v: haha[a]) {
if(!bruh[v.second] && dep[v.first] < dep[a]) {
idk.push_back(v.second);
}
}
if(idk.empty()) {
return;
}
int br = calc2(a,idk);
piglin(a,idk,br);
}
}
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);
vector<int> wut(0);
for(int i = 1; i < n; i++) {
wut.push_back(ped[i]);
}
g = count_common_roads(wut);
apple(0,-1);
orange(0,-1);
return ans;
}
