#include "simurgh.h"
#include <stdlib.h>
#include <string.h>
using namespace std;
#define N 240
#define M (N * (N - 1) / 2)
typedef vector<int> vi;
int ds[N], 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;
}
int ii[M], jj[M];
int *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
char cc[M], marked[M];
int dfs(int p, int i, int t) {
int o;
if (i == t)
return 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (j != p && dfs(i, j, t)) {
marked[h] = 1;
return 1;
}
}
return 0;
}
vi hh, hh_;
int k_;
int count(int i, int m) {
int g, m_, k;
memset(ds, -1, n * sizeof *ds);
m_ = 0;
for (g = 0; g < m; g++) {
int h = eh[i][g];
join(ii[h], jj[h]);
hh_[m_++] = h;
}
k = 0;
for (g = 0; g < n - 1; g++)
if (join(ii[hh[g]], jj[hh[g]]))
hh_[m_++] = hh[g];
else if (cc[hh[g]])
k++;
return count_common_roads(hh_) - k_ + k;
}
void solve(int i, int l, int r, int a, int b) {
int m, c;
if (a == b)
return;
if (r - l == 1) {
cc[eh[i][l]] = 1;
return;
}
m = (l + r) / 2;
c = count(i, m);
solve(i, l, m, a, c), solve(i, m, r, c, b);
}
vi find_roads(int n_, vi ii_, vi jj_) {
int m = ii_.size(), m_, g, h, i;
n = n_;
for (h = 0; h < m; h++)
ii[h] = ii_[h], jj[h] = jj_[h];
hh.resize(n - 1), hh_.resize(n - 1);
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
m_ = 0;
for (h = 0; h < m; h++)
if (join(ii[h], jj[h])) {
hh[m_++] = h, cc[h] = -1;
append(ii[h], h), append(jj[h], h);
} else
cc[h] = -2;
k_ = count_common_roads(hh);
for (h = 0; h < m; h++) {
int upd, c, tmp, k;
if (cc[h] != -2)
continue;
for (g = 0; g < n - 1; g++)
marked[hh[g]] = 0;
dfs(-1, ii[h], jj[h]);
upd = 0;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1) {
upd = 1;
break;
}
if (!upd)
continue;
c = -1;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] != -1) {
tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
c = cc[hh[g]] ^ (k == k_ ? 0 : 1);
break;
}
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1) {
tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
if (k == k_ + 1)
c = 1;
else if (k == k_ - 1)
c = 0;
if (c != -1)
cc[hh[g]] = c ^ (k == k_ ? 0 : 1);
}
if (c == -1)
c = 0;
for (g = 0; g < n - 1; g++)
if (marked[hh[g]] && cc[hh[g]] == -1)
cc[hh[g]] = c;
}
for (h = 0; h < m; h++)
if (cc[h] == -1)
cc[h] = 1;
else if (cc[h] == -2)
append(ii[h], h), append(jj[h], h);
for (i = 0; i < n; i++) {
int o, o_;
for (o = 0, o_ = 0; o < eo[i]; o++) {
h = eh[i][o];
if (cc[h] == -2)
cc[h] = 0, eh[i][o_++] = h;
}
eo[i] = o_;
solve(i, 0, eo[i], 0, count(i, eo[i]));
}
m_ = 0;
for (h = 0; h < m; h++)
if (cc[h] == 1)
hh[m_++] = h;
return hh;
}
