#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int p[500];
int getp(int x) { return p[x] = (x == p[x] ? x : getp(p[x])); }
int uni(int a, int b) {
a = getp(a);
b = getp(b);
if (a == b) return 0;
p[a] = b;
return 1;
}
const int N = 500;
vector<array<int, 2>> adj[N];
vector<int>
dosp(int n, vector<int> u, vector<int> v) {
int m = n*(n-1)/2;
int x, y, z;
vector<int> edg(n), d(n), r(n-1), ans, t(m, 0);
vector<array<int, 2>> ak;
for (int i = 0; i < m; ++i) {
adj[u[i]].pb({v[i],i});
adj[v[i]].pb({u[i],i});
}
int sp = 0;
for (int c = 0; c < n; ++c) {
r.clear();
for (auto x : adj[c])
r.pb(x[1]);
d[c] = count_common_roads(r);
if (d[c] == 1) sp = c;
}
r.clear();
x = 1;
if (sp) x = 0;
for (auto u : adj[x])
if (u[0] != sp) r.pb(u[1]);
r.pb(0);
x = 0; z = 0;
for (auto u : adj[sp]) {
r[n-2] = u[1];
edg[u[0]] = u[1];
y = count_common_roads(r);
if (y > x) {
x = y;
z = u[1];
}
}
t[z] = 1;
ans.pb(z);
r.clear();
for (int i = 0; i < n; ++i) {
if (i == sp) continue;
if (sz(ans) == n-1) break;
y = d[i];
r.clear();
ak.clear();
z = 0;
for (auto u : adj[i]) {
if (t[u[1]]) {
--y;
++z;
r.pb(u[1]);
} else if (u[0] == sp) {
r.pb(u[1]);
} else ak.pb(u);
}
if (y == 0) continue;
int lp = 0; int rp = sz(ak)-1;
int uz = 0;
while (lp < rp) {
int m = (lp+rp)/2;
uz = 0;
for (int j = 0; j < sz(ak); ++j) {
if(j < lp || j > m) {
if (t[edg[ak[j][0]]])
++uz;
r.pb(edg[ak[j][0]]);
}
else
r.pb(ak[j][1]);
}
int vd = count_common_roads(r);
if (vd > uz+z)
rp = m;
else
lp = m+1;
for (int j = 0; j < sz(ak); ++j)
r.pop_back();
}
t[ak[lp][1]] = 1;
ans.pb(ak[lp][1]);
if (y > 1) --i;
}
return ans;
}
vector<int>
find_roads(int n, vector<int> u, vector<int> v) {
int m = sz(u);
if (m == n*(n-1)/2)
return dosp(n, u, v);
vector<int> ans, r, us(m, 0), z, order(m);
iota(order.begin(), order.end(), 0);
shuffle(order.begin(), order.end(), rng);
for (int i = 0; i < n-1; ++i) {
for (int i = 0; i < n; ++i) p[i] = i;
int c = 0;
shuffle(order.begin(), order.end(), rng);
if (sz(ans) == n-1) break;
r = ans;
for (auto x : ans) {
c += uni(u[x], v[x]);
}
int p = 0;
while (c < n-2) {
if (uni(u[order[p]], v[order[p]])) {
++c;
r.pb(order[p]);
}
++p;
}
while (us[order[p]] || getp(u[order[p]]) == getp(v[order[p]]))
++p;
r.pb(order[p]);
z.clear();
z.pb(order[p]);
assert(sz(r) == n-1);
int x = count_common_roads(r);
for (int j = p+1; j < m; ++j) {
if(us[order[j]]) continue;
if (getp(u[order[j]]) == getp(v[order[j]])) continue;
r[n-2] = order[j];
us[order[j]] = 1;
int l = count_common_roads(r);
if (l == x) {
z.pb(order[j]);
} else if (l < x) {
break;
} else if (l > x) {
z.clear(); z.pb(order[j]);
break;
}
}
for (auto j : z)
ans.pb(j);
}
return ans;
}
