// Ignut
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
void Init(int n) {
p.assign(n, 0);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int Get(int v) {
return p[v] == v ? v : p[v] = Get(p[v]);
}
bool Unite(int u, int v) {
u = Get(u), v = Get(v);
if (u == v) return false;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
p[u] = v;
return true;
}
};
const int N = 555;
vector<int> g[N];
bool ans[N * N];
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
for (int i = 0; i < m; i ++) {
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
DSU dsu;
dsu.Init(n);
vector<int> have;
for (int i = 0; i < m; i ++) {
if (dsu.Unite(u[i], v[i])) {
have.push_back(i);
}
}
int cnt = count_common_roads(have);
while (cnt < n - 1) {
vector<int> next_have;
int del_val = -1;
for (int i : have) {
if (ans[i]) continue;
for (int j : have) if (j != i) next_have.push_back(j);
del_val = i;
break;
}
map<int, int> mp;
for (int i : next_have) mp[i] ++;
DSU dsu2; dsu2.Init(n);
for (int i : next_have) dsu2.Unite(u[i], v[i]);
bool got = false;
for (int i = 0; i < m; i ++) {
if (mp.count(i)) continue;
DSU dsu3 = dsu2;
if (!dsu3.Unite(u[i], v[i])) continue;
next_have.push_back(i);
int c = count_common_roads(next_have);
if (c > cnt) {
got = true;
ans[i] = true;
have = next_have;
break;
}
next_have.pop_back();
}
if (!got) {
ans[del_val] = true;
}
cnt = count_common_roads(have);
}
return have;
}
