#include "simurgh.h"
#include <string.h>
using namespace std;
#define N 240
#define M (N * (N - 1) / 2)
typedef vector<int> vi;
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
char cc[M]; int qu[M], cnt;
vi find_roads(int n, vi ii, vi jj) {
int m = ii.size(), m_, g, h, h_, k, k_;
vi hh(n - 1);
memset(cc, -1, m * sizeof *cc);
while (1) {
memset(ds, -1, n * sizeof *ds);
m_ = 0;
for (h = 0; h < m; h++)
if (cc[h] == 1)
join(ii[h], jj[h]), hh[m_++] = h;
if (m_ == n - 1)
break;
g = m_;
for (h = 0; h < m; h++)
if (cc[h] == -1 && join(ii[h], jj[h]))
hh[m_++] = h;
k = count_common_roads(hh);
memset(ds, -1, n * sizeof *ds);
for (h = 0; h < n - 1; h++)
if (h != g)
join(ii[hh[h]], jj[hh[h]]);
h_ = hh[g];
cnt = 0, qu[cnt++] = h_;
for (h = 0; h < m; h++)
if (cc[h] == -1 && h != h_ && find(ii[h]) != find(jj[h])) {
hh[g] = h;
k_ = count_common_roads(hh);
if (k_ == k + 1) {
while (cnt--)
cc[qu[cnt]] = 0;
cc[h] = 1;
break;
} else if (k_ == k - 1) {
while (cnt--)
cc[qu[cnt]] = 1;
cc[h] = 0;
break;
}
qu[cnt++] = h;
}
if (cnt > 0)
while (cnt--)
cc[qu[cnt]] = 1;
}
return hh;
}
