#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 505;
int n, m;
vector<int>u, v, g[lim];
namespace sub12{
vector<int>solve(){
vector<int>in, pi(n), h(n, -1), color(m, -1);
vector<bool>out(m, false);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& i : g[s]){
if(i != pi[s]){
int d = u[i] ^ v[i] ^ s;
if(h[d] == -1){
h[d] = h[s] + 1;
in.push_back(pi[d] = i);
dfs(d);
}
else{
out[i] = true;
}
}
}
};
pi[h[0] = 0] = -1;
dfs(0);
int init_count = count_common_roads(in);
for(int i = 0; i < m; i++){
if(!out[i]){
continue;
}
int x = u[i], y = v[i];
if(h[x] < h[y]){
swap(x, y);
}
vector<int>path;
while(x != y){
path.push_back(pi[x]);
x ^= u[pi[x]] ^ v[pi[x]];
}
vector<int>minus, zero, one;
for(int& j : path){
if(color[j] == -1){
minus.push_back(j);
}
else if(color[j] == 0){
zero.push_back(j);
}
else{
one.push_back(j);
}
}
if(!zero.empty()){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), zero[0]));
ask.push_back(i);
color[i] = count_common_roads(ask) > init_count;
}
else if(!one.empty()){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), one[0]));
ask.push_back(i);
color[i] = count_common_roads(ask) == init_count;
}
else{
vector<int>query(minus.size()), cnt(3, 0);
for(int j = 0; j < minus.size(); j++){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), minus[j]));
ask.push_back(i);
cnt[(query[j] = count_common_roads(ask)) - init_count + 1]++;
}
color[i] = cnt[2] > 0;
for(int j = 0; j < minus.size(); j++){
if(color[i]){
color[minus[j]] = query[j] == init_count;
}
else{
color[minus[j]] = query[j] < init_count;
}
}
minus.clear();
}
for(int& j : minus){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), j));
ask.push_back(i);
if(color[i]){
color[j] = count_common_roads(ask) == init_count;
}
else{
color[j] = count_common_roads(ask) < init_count;
}
}
}
for(int& i : in){
if(color[i] == -1){
color[i] = 1;
}
}
vector<int>ans;
for(int i = 0; i < m; i++){
if(color[i] == 1){
ans.push_back(i);
}
}
return ans;
}
}
namespace sub345{
vector<int>solve(){
vector<int>in, pi(n), h(n, -1), color(m, -1);
vector<bool>out(m, false);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& i : g[s]){
if(i != pi[s]){
int d = u[i] ^ v[i] ^ s;
if(h[d] == -1){
h[d] = h[s] + 1;
in.push_back(pi[d] = i);
dfs(d);
}
else{
out[i] = true;
}
}
}
};
pi[h[0] = 0] = -1;
dfs(0);
int init_count = count_common_roads(in);
for(int i = 0; i < m; i++){
if(!out[i]){
continue;
}
int x = u[i], y = v[i];
if(h[x] < h[y]){
swap(x, y);
}
vector<int>path;
while(x != y){
path.push_back(pi[x]);
x ^= u[pi[x]] ^ v[pi[x]];
}
vector<int>minus, zero, one;
for(int& j : path){
if(color[j] == -1){
minus.push_back(j);
}
else if(color[j] == 0){
zero.push_back(j);
}
else{
one.push_back(j);
}
}
if(minus.empty()){
continue;
}
if(!zero.empty()){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), zero[0]));
ask.push_back(i);
color[i] = count_common_roads(ask) > init_count;
}
else if(!one.empty()){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), one[0]));
ask.push_back(i);
color[i] = count_common_roads(ask) == init_count;
}
else{
vector<int>query(minus.size()), cnt(3, 0);
for(int j = 0; j < minus.size(); j++){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), minus[j]));
ask.push_back(i);
cnt[(query[j] = count_common_roads(ask)) - init_count + 1]++;
}
color[i] = cnt[2] > 0;
for(int j = 0; j < minus.size(); j++){
if(color[i]){
color[minus[j]] = query[j] == init_count;
}
else{
color[minus[j]] = query[j] < init_count;
}
}
minus.clear();
}
for(int& j : minus){
vector<int>ask = in;
ask.erase(find(ask.begin(), ask.end(), j));
ask.push_back(i);
if(color[i]){
color[j] = count_common_roads(ask) == init_count;
}
else{
color[j] = count_common_roads(ask) < init_count;
}
}
}
for(int& i : in){
if(color[i] == -1){
color[i] = 1;
}
}
for(int x = 0; x < n; x++){
vector<int>bin;
for(int& i : g[x]){
if(color[i] == -1 && h[x] < h[u[i] ^ v[i] ^ x]){
bin.push_back(i);
}
}
int pre = 0;
while(true){
int low = pre, high = int(bin.size() - 1), pos = -1;
while(low <= high){
int mid = (low + high) >> 1, expect = init_count;
vector<int>ask = in;
for(int i = 0; i <= mid; i++){
int y = u[bin[i]] ^ v[bin[i]] ^ x;
if(color[pi[y]]){
expect--;
}
ask.erase(find(ask.begin(), ask.end(), pi[y]));
ask.push_back(bin[i]);
}
if(count_common_roads(ask) == expect){
low = mid + 1;
}
else{
high = (pos = mid) - 1;
}
}
if(pos == -1){
break;
}
color[bin[pre = pos]] = 1;
bin.erase(bin.begin() + pos);
}
}
vector<int>ans;
for(int i = 0; i < m; i++){
if(color[i] == 1){
ans.push_back(i);
}
}
assert(ans.size() == n - 1);
return ans;
}
}
vector<int>find_roads(int _n, vector<int>_u, vector<int>_v){
swap(u, _u);
swap(v, _v);
m = u.size();
for(int i = 0; i < m; i++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
n = _n;
if((n = _n) <= 50){
return sub12::solve();
}
return sub345::solve();
}
