#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int MAXM = 250001;
int N,g;
vector<pair<int,int>> haha[MAXN];
vector<int> dep(MAXN,-1);
vector<bool> bruh(MAXM);
vector<int> ped(MAXN);
vector<int> ted(MAXN,-1);
vector<int> ans(0);
vector<int> par(MAXN);
vector<pair<int,int>> edge(0);
void dfs(int a, int d) {
dep[a] = d;
for(pair<int,int> v: haha[a]) {
if(dep[v.first] == -1) {
dfs(v.first,d+1);
bruh[v.second] = true;
ped[v.first] = v.second;
par[v.first] = a;
}
}
}
int calc(int x, int t) {
int n = N;
vector<int> yo(0);
for(int j = 1; j < n; j++) {
if(j != x) {
yo.push_back(ped[j]);
}
}
yo.push_back(t);
return count_common_roads(yo);
}
int dude(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 orange(int x, vector<int> idk, int br) {
if(br == 0 || idk.empty()) {
return;
}
if(idk.size() == 1) {
ans.push_back(idk[0]);
return;
}
vector<int> a(0);
vector<int> b(0);
int s = idk.size();
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 = dude(x,a);
orange(x,a,y);
orange(x,b,br-y);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
vector<int> wow(0);
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);
for(int i = 1; i < n; i++) {
wow.push_back(ped[i]);
}
g = count_common_roads(wow);
for(int i = 0; i < m; i++) {
if(!bruh[i]) {
int a = u[i],b = v[i];
if(dep[a] < dep[b]) {
swap(a,b);
}
vector<pair<int,int>> wut(0);
int br = 0;
while(a != b) {
wut.push_back({a,ted[a]});
if(ted[a] == -1) {
br++;
}
a = par[a];
}
if(br == 0) {
continue;
}
if(br == wut.size()) {
vector<int> troll(wut.size());
int c = 0;
for(int j = 0; j < wut.size(); j++) {
pair<int,int> v = wut[j];
int x = calc(v.first,i);
if(x > g) {
c = 1;
}
if(x != g) {
troll[j] = 1;
}
}
for(int j = 0; j < wut.size(); j++) {
if(c) {
troll[j] = 1-troll[j];
}
ted[wut[j].first] = troll[j];
}
}
else {
int c;
for(pair<int,int> v: wut) {
if(v.second != -1) {
if(calc(v.first,i) == g) {
c = v.second;
}
else {
c = 1-v.second;
}
break;
}
}
for(pair<int,int> v: wut) {
if(v.second == -1) {
int z = c;
if(calc(v.first,i) != g) {
z = 1-c;
}
ted[v.first] = z;
}
}
}
}
}
for(int i = 1; i < n; i++) {
if(ted[i] == -1) {
ted[i] = 1;
}
if(ted[i]) {
ans.push_back(ped[i]);
}
}
for(int i = 1; i < n; i++) {
vector<int> idk(0);
for(pair<int,int> v: haha[i]) {
if(!bruh[v.second] && dep[v.first] < dep[i]) {
idk.push_back(v.second);
}
}
if(idk.empty()) {
continue;
}
int br = dude(i,idk);
orange(i,idk,br);
}
return ans;
}
