#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 550;
int N;
pii par[mxn];
vector<pii> paths[mxn];
vector<pii> tree[mxn];
vector<int> back_edge;
int tp[mxn*mxn];
vector<pii> edges;
int dep[mxn];
vector<int> tree_edge;
set<int> tree_st;
int normal = 0;
/*
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
return r;
r[0] = n - 1;
return r;
*/
struct DSU{
int dsu[mxn],sz[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
fill(sz,sz+mxn,1);
}
void init(){
iota(dsu,dsu+mxn,0);
fill(sz,sz+mxn,1);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(sz[a]<sz[b])swap(a,b);
sz[a] += sz[b];
dsu[b] = a;
}
};
DSU dsu;
void dfs(int now,int fa){
for(auto &[nxt,id]:paths[now]){
if(nxt == fa)continue;
if(par[nxt].fs == -1){
tree_edge.push_back(id);
par[nxt] = pii(now,id);
dep[nxt] = dep[now]+1;
dfs(nxt,now);
}
else{
back_edge.push_back(id);
}
}
return;
}
int C = 0;
int ask(vector<int> &v){
C++;
assert(C<=30000);
int re = count_common_roads(v);
return re;
}
int ask(set<int> &st){
vector<int> v;
for(auto &i:st)v.push_back(i);
return ask(v);
}
void solve_cycle(vector<int> &v,int eid){
vector<int> res;
auto st = tree_st;
st.insert(eid);
for(auto &i:v){
st.erase(i);
res.push_back(ask(st));
st.insert(i);
}
st.erase(eid);
int mn = *min_element(res.begin(),res.end());
int mx = *max_element(res.begin(),res.end());
//cerr<<"CYCLE: "<<mx<<' '<<mn<<endl;for(auto &i:v)cerr<<i<<',';cerr<<endl;for(auto &i:res)cerr<<i<<',';cerr<<endl;
if(mn == mx){
if(normal == mn){
tp[eid] = 0;
for(auto &i:v)tp[i] = 0;
}
else if(normal<mn){
tp[eid] = 1;
for(auto &i:v)tp[i] = 0;
}
else if(normal>mn){
tp[eid] = 0;
for(auto &i:v)tp[i] = 1;
}
}
else{
assert(mx-mn == 1);
if(mx>normal)tp[eid] = 1;
else tp[eid] = 0;
for(int i = 0;i<v.size();i++){
if(res[i] == mx)tp[v[i]] = 0;
else tp[v[i]] = 1;
}
}
return;
}
void solve(int eid){
auto [a,b] = edges[eid];
if(dep[a]>dep[b])swap(a,b);
int tmp = b;
vector<int> v;
while(tmp != a){
v.push_back(par[tmp].sc);
tmp = par[tmp].fs;
//cerr<<v.back()<<','<<tmp<<' '<<a<<endl;
}
//cerr<<"SOLVE: "<<eid<<"::";for(auto &i:v)cerr<<i<<',';cerr<<endl;
int checker = -1;
bool done = true;
for(auto &i:v){
if(tp[i] == -1)done = false;
if(tp[i] != -1)checker = i;
}
if(done)return;
if(checker == -1)solve_cycle(v,eid);
else{
auto st = tree_st;
st.erase(checker);
st.insert(eid);
int re = ask(st);
if(re == normal)tp[eid] = tp[checker];
else tp[eid] = tp[checker]^1;
st.erase(eid);
st.insert(checker);
//cerr<<"CHECKER: "<<checker<<','<<re<<endl;
for(auto &i:v){
if(tp[i] == -1){
auto [a,b] = edges[i];
st.erase(i);
st.insert(eid);
//cerr<<i<<"::";for(auto &j:st)cerr<<j<<',';cerr<<ask(st)<<endl;
if(ask(st) == normal)tp[i] = tp[eid];
else tp[i] = tp[eid]^1;
st.insert(i);
st.erase(eid);
}
}
}
//cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
return;
}
int get_num(vector<int> &tar){
dsu.init();
vector<int> v;
for(auto &i:tar){
auto [a,b] = edges[i];
if(dsu.root(a) == dsu.root(b)){
cerr<<"WA: not forest!"<<endl;
assert(false);
}
dsu.onion(a,b);
v.push_back(i);
}
int s = 0;
for(auto &i:tree_edge){
if(tp[i] == -1){
cerr<<"WA tree not known!"<<endl;
assert(false);
}
auto [a,b] = edges[i];
if(dsu.root(a) == dsu.root(b))continue;
dsu.onion(a,b);
v.push_back(i);
s += tp[i];
}
if(v.size() != N-1){
cerr<<"WA: not asking a tree!"<<endl;
cerr<<v.size()<<endl;
assert(false);
}
int re = ask(v);
return re-s;
}
void dc(vector<int> edges,int cnt){
if(!cnt||edges.empty())return;
if(cnt == edges.size()){
for(auto &i:edges){
tp[i] = 1;
}
return;
}
vector<int> lv,rv;
int mid = edges.size()>>1;
for(int i = 0;i<edges.size();i++){
if(i<mid)lv.push_back(edges[i]);
else rv.push_back(edges[i]);
}
int lc = get_num(lv),rc = cnt-lc;
dc(lv,lc);dc(rv,rc);
}
void calc(int now){
vector<int> edges;
for(auto [_,id]:paths[now]){
if(tp[id] == -1)edges.push_back(id);
}
dc(edges,get_num(edges));
for(auto &i:edges){
if(tp[i] == -1)tp[i] = 0;
}
return;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
memset(tp,-1,sizeof(tp));
for(auto &i:par)i = pii(-1,-1);
for(int i = 0;i<u.size();i++){
int a = u[i],b = v[i];
edges.push_back(pii(a,b));
paths[a].push_back(pii(b,i));
paths[b].push_back(pii(a,i));
}
par[0] = pii(0,-1);
dfs(0,0);
sort(back_edge.begin(),back_edge.end());
back_edge.resize(unique(back_edge.begin(),back_edge.end())-back_edge.begin());
for(auto &i:tree_edge)tree_st.insert(i);
//cerr<<"TREE :";for(auto &i:tree_edge)cerr<<i<<',';cerr<<endl;
normal = ask(tree_edge);
//cerr<<"NORMAL: "<<normal<<endl;
for(auto &i:back_edge)solve(i);
for(auto &i:tree_edge){
if(tp[i] == -1)tp[i] = 1;
}
for(int i = 0;i<N;i++){
calc(i);
}
vector<int> ans;
for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
//cerr<<C<<" ASKS"<<endl;
//cerr<<"ANS: ";for(auto &i:ans)cerr<<i<<',';cerr<<endl;
return ans;
}
