#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef __int128 i128;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 550;//100100*20;
const ll MOD = 1e9+7;
const ll INF = 2e9;
int par[MAXN];
void init() { for(int i=0; i<MAXN; i++) par[i]=i; }
int root(int x) { return par[x]==x?x:par[x]=root(par[x]); }
void merge(int x, int y) { x = root(x), y = root(y); if(x^y) par[x]=y; }
vector<pi> edge;
vector<pi> adj[MAXN], graph[MAXN];
queue<int> q;
bool vst[MAXN];
pi pv[MAXN];
vector<int> tree;
vector<int> ans;
vector<pi> tmp[MAXN];
bool chk[MAXN*MAXN];
vector<int> input;
int dnc(int x, int s, int e) {
init(); input.clear();
for(int i=s; i<=e; i++) {
input.push_back(adj[x][i].ss);
merge(x, adj[x][i].ff);
}
int res=0;
for(int t : tree) {
int a=root(edge[t].ff), b=root(edge[t].ss);
if(a^b) {
res -= chk[t];
input.push_back(t);
par[a]=b;
}
} res += count_common_roads(input);
if(res == 0) return res;
if(res == e-s+1) {
for(int i=s; i<=e; i++) ans.push_back(adj[x][i].ss);
return res;
}
// if(s == e) {
// ans.push_back(adj[x][s].ss);
// return;
// }
int mid = s+e>>1;
int z = dnc(x, s, mid);
if(z < res) dnc(x, mid+1, e);
return res;
}
void compute(int n, int x) {
int m = edge.size();
init(); input.clear();
for(int i=0; i<m; i++) {
if(edge[i].ff == x || edge[i].ss == x) continue;
int a = root(edge[i].ff), b = root(edge[i].ss);
if(a^b) {
par[a] = b;
input.push_back(i);
}
}
for(int i=0; i<n; i++) tmp[i].clear();
for(auto [y,w] : graph[x]) {
tmp[root(y)].push_back(pi(0, w));
}
for(int i=0; i<n; i++) {
if(tmp[i].empty()) continue;
int cnt=0;
for(int j=0; j<n; j++) {
if(tmp[j].size() && j!=i) {
cnt++;
input.push_back(tmp[j][0].ss);
}
}
for(auto &[y, w] : tmp[i]) {
input.push_back(w);
y = count_common_roads(input);
input.pop_back();
}
sort(all(tmp[i]), greater<pi>());
int t = tmp[i].begin()->ff;
if(!(t == tmp[i].rbegin()->ff && x && root(pv[x].ff)==i && chk[pv[x].ss]==0))
for(auto it=tmp[i].begin(); it!=tmp[i].end()&&it->ff==t; it++) chk[it->ss]=1;
while(cnt--) input.pop_back();
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m = u.size();
for(int i=0; i<m; i++) {
edge.push_back(pi(u[i], v[i]));
adj[u[i]].push_back(pi(v[i], i));
adj[v[i]].push_back(pi(u[i], i));
}
// construct bfs-tree and compute for that tree
q.push(0); vst[0] = 1;
while(q.size()) {
int here = q.front(); q.pop();
for(auto [there,w] : adj[here]) {
if(vst[there]) continue;
pv[there] = pi(here, w);
graph[here].push_back(pi(there, w));
tree.push_back(w);
q.push(there); vst[there] = 1;
}
if(here) graph[here].push_back(pv[here]);
compute(n, here);
}
// for(int x:tree)cout<<x<<bl;cout<<endl;
// for(int i=0;i<m;i++) cout<<chk[i]<<bl;cout<<endl;
for(int i=0; i<n; i++) adj[i].clear();
for(int i=0; i<m; i++) {
adj[u[i]].push_back(pi(v[i], i));
}
// binary search for each vertex
for(int x=0; x<n; x++) {
if(adj[x].size()) dnc(x, 0, (int)adj[x].size()-1);
} return ans;
}
