#include "simurgh.h"
#include <bits/stdc++.h>
#define maxn 505
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int nho[maxn][maxn], cnt[maxn], cool[maxn], nexCool[maxn];
int pp = 0;
int countCommonRoads(const vector<int> &indice) {
assert(++pp <= 8000);
return count_common_roads(indice);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
for (int i = 0; i < m; i++) nho[u[i]][v[i]] = nho[v[i]][u[i]] = i;
vector<int> cl(m, 0);
for (int i = 0; i < n; i++) {
vector<int> indice;
for (int j = 0; j < n; j++) if (i != j) indice.emplace_back(nho[i][j]);
cnt[i] = countCommonRoads(indice);
if (cnt[i] == n-1) return indice;
}
for (int i = 0; i < n-1; i++) {
int mn = INT_MAX;
vector<int> indice;
if (i == 0) {
for (int j = 1; j < n-1; j++) indice.emplace_back(nho[j][j+1]);
} else if (i == n-1) {
for (int j = 0; j < n-2; j++) indice.emplace_back(nho[j][j+1]);
} else {
for (int j = 0; j < i-1; j++) indice.emplace_back(nho[j][j+1]);
indice.emplace_back(nho[i-1][i+1]);
for (int j = i+1; j < n-1; j++) indice.emplace_back(nho[j][j+1]);
}
int dem = 0;
for (int o = 0; o < n; o++)
if (o != i) {
indice.emplace_back(nho[o][i]);
mn = min(mn, countCommonRoads(indice));
indice.pop_back();
if (++dem > cnt[i]) break;
}
indice.emplace_back(nho[i][i+1]);
cool[i] = (countCommonRoads(indice) != mn);
indice.pop_back();
if (i < n-2) {
indice.emplace_back(nho[i][i+2]);
nexCool[i] = (countCommonRoads(indice) != mn);
}
if (cool[i]) cl[nho[i][i+1]] = 1;
}
for (int o = 0; o < n; o++) {
vector<int> lis;
for (int i = 0; i < n; i++) if (o != i) lis.emplace_back(i);
for (int p = 1; p <= cnt[o]; p++) {
function<int(int)> ok = [&](int x) {
vector<int> indice;
for (int i = 0; i <= x; i++)
indice.emplace_back(nho[o][lis[i]]);
for (int i = x; i < n-2; i++)
indice.emplace_back(nho[lis[i]][lis[i+1]]);
int ans = countCommonRoads(indice);
for (int i = x; i < n-2; i++) {
if (lis[i] + 1 == lis[i+1]) ans -= cool[lis[i]];
else ans -= nexCool[lis[i]];
}
return ans;
};
int lo = -1, hi = n-2;
while (hi-lo > 1) {
int mid = (lo + hi) >> 1;
if (ok(mid) >= p) hi = mid;
else lo = mid;
}
cl[nho[o][lis[hi]]] = 1;
}
}
vector<int> ans;
for (int i = 0; i < m; i++) if (cl[i] == 1) ans.emplace_back(i);
return ans;
}
/*
5 5
0 1
0 2
0 3
0 4
1 4
0 1 2 3
*/
