#include "simurgh.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
struct DSU {
int n;
vi dad,sz;
vector<vi> v;
DSU(int nn) {
n = nn;
dad.resize(n);
v.resize(n);
sz.assign(n,1);
for (int i = 0;i<n;i++) v[i].push_back(i);
iota(all(dad),0ll);
}
int find(int x) {
if (x == dad[x]) return x;
return dad[x] = find(dad[x]);
}
bool unite(int x,int y) {
int a = find(x),b = find(y);
if (a == b) return false;
if (sz[a] > sz[b]) swap(a,b);
dad[a] = b;
sz[b]+=sz[a];
for (auto it : v[a]) v[b].push_back(it);
v[a].clear();
sz[a] = 0;
return true;
}
};
int cache[501][501],got[501][501];
int oldie;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m = u.size();
DSU dsu(n);
vi mst;
memset(got,-1,sizeof got);
memset(cache,-1,sizeof cache);
for (int i = 0;i<m;i++) {
got[u[i]][v[i]] = got[v[i]][u[i]] = i;
if (dsu.unite(u[i],v[i])) {
mst.push_back(i);
}
}
assert(mst.size() == n-1);
oldie = count_common_roads(mst);
set<int> ans;
for (int i = 0;i<n-1;i++) {
int road = mst[i];
DSU dsu2(n);
vi mstt;
for (int j = 0;j<n-1;j++) {
if (j != i) {
dsu2.unite(u[mst[j]],v[mst[j]]);
mstt.push_back(mst[j]);
}
}
int found = 0;
int bad = 0,good = 0;
for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
if (found) break;
for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
if (found) break;
int a = A,b = B;
if (a > b) swap(a,b);
if (got[a][b] == -1) continue;
if (cache[a][b] != -1) {
found = 1;
mstt.push_back(got[a][b]);
int nw = count_common_roads(mstt);
if (nw > oldie) bad = 1;
else if (nw < oldie) good = 1;
else {
if (cache[a][b] == 0) bad = 1;
else good = 1;
}
mstt.pop_back();
break;
}
}
}
if (!found) {
for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
int a = A,b = B;
if (a > b) swap(a,b);
if (got[a][b] == -1) continue;
mstt.push_back(got[a][b]);
int nw = count_common_roads(mstt);
if (nw > oldie) {
bad = 1;
ans.insert(got[a][b]);
cache[a][b] = 1;
}
else if (nw < oldie) {
good = 1;
cache[a][b] = 0;
}
mstt.pop_back();
}
}
}
if (!bad && !good) {
if (!good) {
for (auto A : dsu2.v[dsu2.find(u[mst[i]])]) {
for (auto B : dsu2.v[dsu2.find(v[mst[i]])]) {
int a = A,b = B;
if (a > b) swap(a,b);
if (got[a][b] == -1) continue;
if (cache[a][b] != -1) continue;
cache[a][b] = 1;
ans.insert(got[a][b]);
}
}
}
}
else {
if (!bad) ans.insert(mst[i]);
for (auto A : dsu2.v[dsu2.find(u[mst[i]])]) {
for (auto B : dsu2.v[dsu2.find(v[mst[i]])]) {
int a = A,b = B;
if (a > b) swap(a,b);
if (got[a][b] == -1) continue;
if (cache[a][b] != -1) continue;
mstt.push_back(got[a][b]);
int nw = count_common_roads(mstt);
if (nw <= oldie) {
cache[a][b] = 0;
}
else {
cache[a][b] = 1;
ans.insert(got[a][b]);
}
mstt.pop_back();
}
}
}
}
vi vv;
for (auto it : ans) vv.push_back(it);
return vv;
}
