#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
set<int>adj[505];
map<pair<int, int>, int>mp;
int roads;
bool vis[505];
int a[200000], val[200000], par[505], l[505];
int timer=0;
pair<int, int>cur={-1, -1};
void dfs(int x, int p){
vis[x]=true;
par[x]=p;
l[x]=timer++;
for(int y:adj[x]){
if(!vis[y]) dfs(y, x);
else if(y!=p && l[y]<=l[x]){
cur={x, y};
}
}
}
vector<int>test, query, oq;
void bfs(){
memset(vis, false, sizeof vis);
queue<int>q;
for(int i=0;i<test.size()-1;i++){
vis[test[i]]=true;
q.push(test[i]);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int y:adj[x]){
if(!vis[y]){
q.push(y);
vis[y]=true;
query.push_back(mp[{x, y}]-1);
}
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m=u.size();
roads=m;
for(int i=0;i<m;i++){
adj[u[i]].insert(v[i]);
adj[v[i]].insert(u[i]);
mp[{u[i], v[i]}]=i+1;
mp[{v[i], u[i]}]=i+1;
}
while(roads>=n){
//cout<<roads<<endl;
memset(vis, false, sizeof vis);
dfs(0, -1);
int x=cur.first, y=cur.second, ox=cur.first;
test.clear();
while(x!=y){
test.push_back(x);
x=par[x];
}
test.push_back(y);
test.push_back(ox);
/*for(int i:test) cout<<i<<" ";
cout<<endl;*/
query.clear();
bfs();
int mini=0, sz=test.size();
for(int i=0;i<sz-1;i++){
oq=query;
if(a[mp[{test[i], test[i+1]}]]!=0) continue;
for(int j=0;j<sz-1;j++){
if(j!=i) query.push_back(mp[{test[j], test[j+1]}]-1);
}
/*cout<<"querying ";
for(int i:query) cout<<i<<" ";
cout<<endl;*/
val[i]=count_common_roads(query);
mini=max(mini, val[i]);
query=oq;
}
for(int i=0;i<sz-1;i++){
if(a[mp[{test[i], test[i+1]}]]!=0) continue;
if(val[i]==mini){
//cout<<"delet "<<test[i]<<" "<<test[i+1]<<": "<<mp[{test[i], test[i+1]}]-1<<endl;
a[mp[{test[i], test[i+1]}]]=1;
adj[test[i]].erase(test[i+1]);
adj[test[i+1]].erase(test[i]);
roads--;
}
else{
//cout<<"fix "<<test[i]<<" "<<test[i+1]<<": "<<mp[{test[i], test[i+1]}]-1<<endl;
a[mp[{test[i], test[i+1]}]]=2;
}
}
}
vector<int>ans;
for(int i=0;i<m;i++){
if(a[i+1]!=1) ans.push_back(i);
}
return ans;
}
