#include "simurgh.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
ll W[250000];
ll N, z, D[500], X[500], Y[500], P[500], E[500], dsuP[500];
vector <array<ll, 3>> Z;
vector <array<ll, 2> > adj[500];
void dfs(ll u, ll w) {
D[u] = w;
for (auto [v, x] : adj[u]) {
if (D[v] == -1) {
P[v] = u, E[v] = x;
dfs(v, w+1);
}
else if (D[v] < D[u]-1 && D[v] < X[u]) {
X[u] = D[v], Y[u] = x;
}
}
}
ll query(ll x, ll y) {
vector <int> Q;
for (auto [u, a, b] : Z) {
if (u == x) Q.push_back(y);
else Q.push_back(u);
}
return count_common_roads(Q);
}
ll dsu(ll u) {
if (dsuP[u] == u) return u;
else return dsuP[u] = dsu(dsuP[u]);
}
ll bsquery(ll u, vector <array<ll, 2>> V) {
for (int i=0; i<N; ++i) dsuP[i] = i;
vector <int> Q;
ll w = 0;
for (auto [x, y] : V) {
ll a = dsu(u), b = dsu(x);
dsuP[a] = b;
Q.push_back(y);
}
for (auto [y, a, b] : Z) {
a = dsu(a), b = dsu(b);
if (a != b) {
dsuP[a] = b;
Q.push_back(y);
w += W[y];
}
}
return count_common_roads(Q) - w;
}
void solve(ll u) {
if (X[u] != 1e18) {
vector <array<ll, 2> > V;
ll v = u;
while (D[v] != X[u] && W[E[v]] == -1) {
V.push_back({E[v], 0});
v = P[v];
}
for (int i=0; i<V.size(); ++i) {
V[i][1] = query(V[i][0], Y[u]);
}
V.push_back({Y[u], z});
sort(V.begin(), V.end(), [](auto a, auto b) {
return a[1] > b[1];
});
if (V[0][1] == V.back()[1]) {
for (auto [x, y] : V) W[x] = 0;
}
else {
for (int i=0; i<V.size(); ++i) {
if (V[i][1] != V.back()[1]) W[V[i][0]] = 0;
else W[V[i][0]] = 1;
}
}
}
for (auto [v, x] : adj[u]) {
if (D[v] != D[u]+1) continue;
solve(v);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
for (int i=0; i<n; ++i) D[i] = -1, X[i] = 1e18;
for (int i=0; i<u.size(); ++i) {
W[i] = -1;
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
P[0] = -1;
dfs(0, 0);
for (int i=1; i<n; ++i) Z.push_back({E[i], i, P[i]});
z = query(-1, -1);
solve(0);
for (int i=1; i<n; ++i) {
if (W[E[i]] == -1) W[E[i]] = 1;
}
vector <int> F;
for (int i=0; i<n; ++i) {
vector <array<ll, 2> > V;
for (auto [x, y] : adj[i]) {
if (i < x) V.push_back({x, y});
}
while (!V.empty()) {
if (!bsquery(i, V)) break;
ll l = 0, r = (ll)V.size()-1, mid;
while (l < r) {
mid = (l+r)/2;
vector <array<ll, 2>> tmp;
for (int j=l; j<=mid; ++j) tmp.push_back(V[j]);
if (bsquery(i, tmp)) r = mid;
else l = mid+1;
}
F.push_back(V[l][1]);
swap(V[l], V[(ll)V.size()-1]);
V.pop_back();
}
}
return F;
}
