using namespace std;
#include <vector>
#define vi vector<int>
#include "simurgh.h"
#define pi pair<int,int>
#include <random>
#define x first
#define y second
const int siz = 501;
int ans[siz][siz];
int in[siz][siz];
vi fr[siz];
int h[siz];
int pad[siz];
vi u, v;
int n;
bool vis[siz];
vi tr;
int m;
void dfs(int i) {
if (vis[i])return;
vis[i] = 1;
for (int f : fr[i]) {
if (!vis[f]) {
h[f] = h[i] + 1;
pad[f] = i;
tr.push_back(in[i][f]);
dfs(f);
}
}
}
static int find(int node, vi&parent) {
return (parent[node] == node ? node : parent[node] = find(parent[node],parent));
}
static bool merge(int v1, int v2, vi& parent, vi& siz) {
v1 = find(v1,parent);
v2 = find(v2,parent);
if (v1 == v2)
return false;
if (siz[v1] > siz[v2])swap(v1, v2);
parent[v1] = v2;
if (siz[v1] == siz[v2])siz[v2]++;
return true;
}
int common(vi ed) {
int mi = 0;
vi q = ed;
vi parent(n); for (int i = 0; i < n; i++)parent[i] = i;
vi siz(n);
for (int i : ed)merge(u[i], v[i],parent,siz);
for (int i : tr) {
if (merge(u[i], v[i], parent, siz)) {
if(ans[u[i]][v[i]]==1)mi++;
q.push_back(i);
}
}
return count_common_roads(q) - mi;
}
void check(vi ed, int f) {
if (ed.size() == 1) {
ans[u[ed[0]]][v[ed[0]]] = 1;
return;
}
int s = ed.size();
vi vec1, vec2;
for (int i = 0; i < s; i++) {
if (i < s / 2)vec1.push_back(ed[i]);
else vec2.push_back(ed[i]);
}
int h = common(vec1);
if (h>0) {
check(vec1, h);
}
if (f-h>0)check(vec2, f-h);
}
vi find_roads(int N, vi U, vi V) {
u = U, v = V;
n = N;
m = u.size();
for (int i = 0; i < m; i++) {
fr[u[i]].push_back(v[i]);
fr[v[i]].push_back(u[i]);
ans[u[i]][v[i]] = -1;
ans[v[i]][u[i]] = -1;
in[u[i]][v[i]] = i;
in[v[i]][u[i]] = i;
}
dfs(0);
int a = count_common_roads(tr);
for (int i = 0; i < n; i++) {
pi p={1e9,1e9};
for (int j : fr[i]) {
p = min(p, { h[j],j });
}
vi cyc = {in[i][p.y]};
if (p.x >= h[i] - 1)continue;
int t = i;
while (t != p.y) {
cyc.push_back({ in[t][pad[t]] });
t = pad[t];
}
vi can = { a };
vi ts(2,-1);
for (int ed : cyc) {
if (ed == cyc[0])continue;
vi q = {cyc[0]};
if (ans[u[ed]][v[ed]] != -1 && ts[ans[u[ed]][v[ed]]] != -1) {
can.push_back(ts[ans[u[ed]][v[ed]]]); continue;
}
for (int j : tr) {
if (j != ed) {
q.push_back(j);
}
}
int b = count_common_roads(q);
can.push_back(b);
if (ans[u[ed]][v[ed]] != -1)ts[ans[u[ed]][v[ed]]] = b;
}
int maxi = a;
for (int j : can)maxi = max(j, maxi);
for (int j = 0; j < can.size(); j++) {
if (can[j] < maxi) {
ans[u[cyc[j]]][v[cyc[j]]] = 1;
}
else ans[u[cyc[j]]][v[cyc[j]]] = 0;
}
}
for (int i : tr)if (ans[u[i]][v[i]] == -1)ans[u[i]][v[i]] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ans[i][j] != -1)ans[j][i] = ans[i][j];
}
}
for (int d = 1; d < n; d++) {
vi vec;
for (int i = 0; i + d < n; i++) {
if (ans[i][i + d] == -1)vec.push_back(in[i][i + d]);
}
int h = common(vec);
if(h)check(vec,h);
}
vi res;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (ans[i][j] == 1 || ans[j][i] == 1)res.push_back(in[i][j]);
}
}
return res;
}
