#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_roads(int n, vector<int> u, vector<int> v){
int m = u.size();
set<int> graph;
vector<set<pair<int,int>>> adj(n);
vector<bool> confirmed(m);
function<bool(int,int,int)> finder = [&](int x,int p,int tar) {
if(x==tar)return true;
for(auto[v,idx]:adj[x])if(v!=p)if(finder(v,x,tar))return true;
return false;
};
auto differential = [&](int x){
stack<int> edges;
function<bool(int,int)> dfs = [&](int xx,int p) {
if(xx==v[x])return true;
for(auto[v,idx]:adj[xx])if(v!=p){
edges.emplace(idx);
if(dfs(v,xx))return true;
edges.pop();
}
return false;
};
dfs(u[x],-1);
if(edges.empty()) {
graph.insert(x);
adj[u[x]].emplace(v[x],x);
adj[v[x]].emplace(u[x],x);
}
vector<int> finaledges;
while(!edges.empty()) {
finaledges.emplace_back(edges.top());
edges.pop();
}
vector<int> sameas;
bool included = false;
for(int&i:finaledges) {
if(confirmed[i])continue;
auto base = count_common_roads(vector(graph.begin(),graph.end()));
graph.erase(i);
graph.insert(x);
auto diff = count_common_roads(vector(graph.begin(),graph.end()));
graph.erase(x);
graph.insert(i);
if(diff==base) {
sameas.emplace_back(i);
continue;
}
if(diff>base) {
included=true;
graph.erase(i);
adj[u[i]].erase({v[i],i});
adj[v[i]].erase({u[i],i});
}
break;
}
if(included) {
graph.insert(x);
adj[u[x]].emplace(v[x],x);
adj[v[x]].emplace(u[x],x);
confirmed[x]=true;
for(int&i:sameas)confirmed[i]=true;
} else {
for(int&i:sameas) {
graph.erase(i);
adj[u[i]].erase({v[i],i});
adj[v[i]].erase({u[i],i});
}
}
};
vector<bool> visited(m);
for(int i=0;i<m;i++) {
if(graph.size()!=n-1) {
for(int j=i;j<m;j++) {
if(visited[j])continue;
if(finder(u[j],-1,v[j])==false) {
visited[j]=true;
graph.insert(j);
adj[u[j]].emplace(v[j],j);
adj[v[j]].emplace(u[j],j);
}
}
}
if(visited[i])continue;
differential(i);
}
return vector(graph.begin(), graph.end());
}
