#include "simurgh.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 500;
vector<pii> adj[MAXN + 10]; // { node, edge id }
struct Tree {
set<int> edge;
int par[MAXN + 10];
int dep[MAXN + 10];
int peid[MAXN + 10];
vector<int> get_edges() {
vector<int> ids;
for(auto &i:edge) ids.eb(i);
return ids;
}
int query() {
// cerr << "query:";
// out();
return count_common_roads(get_edges());
}
void dfs(int x, int p, int d, int pe, bool tree_edge_only = true) {
par[x] = p;
dep[x] = d;
peid[x] = pe;
for(auto &i:adj[x]) if(i.F != p && dep[i.F] == 0) {
if(tree_edge_only && !edge.count(i.S)) continue;
else if(!tree_edge_only) edge.insert(i.S);
dfs(i.F, x, d + 1, i.S, tree_edge_only);
}
}
void add_edge(int a, int b, int id) {
if(edge.count(id)) return;
// cerr << "tree: \n";
// For(i, 0, 3) cerr << par[i] << " \n"[i == 3];
// For(i, 0, 3) cerr << peid[i] << " \n"[i == 3];
memset(dep, 0, sizeof(dep));
dfs(0, -1, 1, -1);
int cnt = query();
while(a != b) {
if(dep[a] < dep[b]) swap(a, b);
int id2 = peid[a];
edge.erase(id2);
edge.insert(id);
// cerr << id2 << " -> " << id << "?\n";
if(query() > cnt) return;
edge.erase(id);
edge.insert(id2);
a = par[a];
}
}
void out() {
for(auto &i:get_edges()) {
cerr << i << " ";
}
cerr << "\n";
}
} tr;
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
int M = sz(U);
For(i, 0, M - 1) {
adj[U[i]].eb(V[i], i);
adj[V[i]].eb(U[i], i);
}
tr.dfs(0, -1, 1, -1, false);
// tr.out();
For(i, 0, M - 1) {
tr.add_edge(U[i], V[i], i);
// tr.out();
}
return tr.get_edges();
// vector<int> r(n - 1);
// for(int i = 0; i < n - 1; i++)
// r[i] = i;
// int common = count_common_roads(r);
// if(common == n - 1)
// return r;
// r[0] = n - 1;
// return r;
}
