//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#define ask count_common_roads
#include "simurgh.h"
int par[501];
vector<pair<int,int>> adj[501];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
int ca=-1;
vector<int> pp;
vector<int> pp2;
void dfs(int no,int par2=-1){
if(no==ca){
pp2=pp;
}
for(auto j:adj[no]){
if(j.a!=par2){
pp.pb(j.b);
dfs(j.a,no);
pp.pop_back();
}
}
}
vector<int> find_roads(int n,vector<int> uu,vector<int> vv) {
int m=uu.size();
for(int i=0;i<n;i++){
par[i]=i;
}
vector<pair<pair<int,int>,int>> cur;
vector<pair<pair<int,int>,int>> cur2;
for(int i=0;i<m;i++){
int x=find(uu[i]);
int y=find(vv[i]);
if(x!=y){
par[x]=y;
cur.pb({{uu[i],vv[i]},i});
adj[uu[i]].pb({vv[i],i});
adj[vv[i]].pb({uu[i],i});
}
else{
cur2.pb({{uu[i],vv[i]},i});
}
}
//mt19937 rng;
//rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
int val;
vector<int> ee;
for(auto j:cur){
ee.pb(j.b);
}
val=ask(ee);
vector<int> ans;
for(int i=0;i<m;i++){
ans.pb(0);
}
for(auto j:cur2){
ca=j.a.b;
dfs(j.a.a);
int cur=-1;
for(auto i:pp2){
if(ans[i]!=0){
cur=i;
}
}
/* for(auto i:pp2){
cout<<i<<",";
}
cout<<endl;*/
if(cur==-1){
vector<pair<int,int>> xx;
xx.pb({val,j.b});
for(auto i:pp2){
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
xx.pb({val2,i});
}
sort(xx.begin(),xx.end());
for(int i=0;i<xx.size();i++){
if(xx[i].a==xx.back().a-1){
ans[xx[i].b]=1;
}
else{
ans[xx[i].b]=-1;
}
}
/*for(auto j:xx){
cout<<j.a<<"::"<<j.b<<endl;
}
cout<<endl;*/
}
else{
if(true){
vector<int> ff;
for(auto jj:ee){
if(jj!=cur){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
int xx=val;
if(ans[cur]==1){
xx--;
}
if(val2==xx){
ans[j.b]=-1;
}
else{
ans[j.b]=1;
}
}
for(auto i:pp2){
if(ans[i]!=0){
continue;
}
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
int xx=val;
if(ans[j.b]==1){
xx+=1;
}
if(val2==xx){
ans[i]=-1;
}
else{
ans[i]=1;
}
}
}
/* for(auto i:ans){
cout<<i<<".";
}
cout<<endl;*/
}
vector<int> ans2;
for(int i=0;i<m;i++){
if(ans[i]==1 or ans[i]==0){
ans2.pb(i);
}
}
// for(int i=0;i<m;i++){
// cout<<ans[i]<<":";
// }
// cout<<endl;
return ans2;
/* shuffle(cur2.begin(),cur2.end(),rng);
for(auto j:cur2){
if(val==n-1){
break;
}
for(int i=0;i<n;i++){
adj[i].clear();
}
for(auto i:cur){
adj[i.a.a].pb({i.a.b,i.b});
adj[i.a.b].pb({i.a.a,i.b});
}
ca=j.a.b;
dfs(j.a.a);
shuffle(pp2.begin(),pp2.end(),rng);
for(auto i:pp2){
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
if(val2<val){
break;
}
if(val2==val){
continue;
}
vector<pair<pair<int,int>,int>> cur3;
for(auto ii:cur){
if(ii.b==i){
continue;
}
cur3.pb(ii);
}
cur3.pb(j);
cur=cur3;
val=val2;
ee=ff;
break;
}
}*/
// return ee;
}
