#include <bits/stdc++.h>
#include "simurgh.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
// #define int long long int
const int N = 10;
const int md = 1e9 + 7;
const int INF = 1e9;
class DisjointSets {
private:
vector<int> p;
public:
DisjointSets(int n) : p(n) {
for (int i = 0; i < n; i++) { p[i] = i;}
}
int get(int u) {
return p[u] = (u == p[u] ? u : get(p[u]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
p[v] = u;
return;
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<pair<int, int>> a;
for (int i = 0; i < (int) u.size(); i++)
a.push_back({u[i], v[i]});
vector<int> ans;
function<void(int, DisjointSets, int, vector<int> )> dfs = [&] (int nd, DisjointSets dsu, int st, vector<int> v) {
if (nd == n - 1) {
if (count_common_roads(v) == (n - 1)) ans = v;
return;
} else {
auto ds = dsu;
for (int i = st; i < (int) a.size(); i++) {
if (dsu.get(a[i].first) != dsu.get(a[i].second)) {
dsu.unite(a[i].first, a[i].second);
v.push_back(i);
dfs(nd + 1, dsu, i + 1, v);
v.pop_back();
dsu = ds;
}
}
}
};
DisjointSets dsu1(n + 1);
dfs(0, dsu1, 0, {});
return ans;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// int n = 7;
// vector<pair<int, int>> a;
// for (int i = 1; i <= n; i++)
// for (int j = i + 1; j <= n; j++) {
// a.push_back({i, j});
// }
// vector<bool> visited((int) a.size() + 1);
// int ans = 0;
// function<void(int, DisjointSets, int)> dfs = [&] (int nd, DisjointSets dsu, int st) {
// if (nd == n - 1) {
// ans++;
// return;
// } else {
// auto ds = dsu;
// for (int i = st; i < (int) a.size(); i++) {
// if (!visited[i] && dsu.get(a[i].first) != dsu.get(a[i].second)) {
// visited[i] = 1;
// dsu.unite(a[i].first, a[i].second);
// dfs(nd + 1, dsu, i + 1);
// dsu = ds;
// visited[i] = 0;
// }
// }
// }
// };
// DisjointSets dsu1(n + 1);
// dfs(0, dsu1, 0);
// cout << ans << '\n';
// }
// return 0;
// }
