#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define getMin(id) min(in[a[id]], in[b[id]])
int N, M, a[250250], b[250250], pe[505], mn[505], mx[505], g[250250], in[505], ch[505], t[250250], cnt;
vector<int> v[505];
int p[250250];
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
void dfs(int u, int p) {
in[u] = ++cnt;
for(auto id : v[u]) {
int x = a[id] ^ b[id] ^ u;
if(x == p) continue;
if(!in[x]) {
pe[x] = mn[x] = ch[u] = id, t[id] = 1;
dfs(x, u);
if(u && getMin(mn[x]) <= getMin(mn[u])) mn[u] = mn[x], mx[u] = mx[x];
} else if(in[x] <= getMin(mn[u])) mn[u] = id, mx[u] = ch[x];
}
}
int query(const set<int> &S) {
return count_common_roads(vector<int>(S.begin(), S.end()));
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
::N = N, M = U.size();
for(int i=0;i<M;i++) {
a[i] = U[i], b[i] = V[i];
v[a[i]].push_back(i);
v[b[i]].push_back(i);
}
dfs(0, -1);
set<int> S;
for(int i=1;i<N;i++) S.insert(pe[i]);
int D = query(S);
if(D == N-1) return vector<int>(S.begin(), S.end());
iota(p, p+M, 0), memset(g, -1, sizeof g);
for(int i=1;i<N;i++) {
if(pe[i] == mn[i]) {
g[pe[i]] = 1;
continue;
}
// cout << i << " " << pe[i] << " " << mn[i] << " " << mx[i] << "\n";
S.erase(pe[i]), S.insert(mn[i]);
int d = query(S);
if(d > D) g[pe[i]] = 0, g[mn[i]] = 1;
if(d < D) g[pe[i]] = 1, g[mn[i]] = 0;
if(d == D) p[find(pe[i])] = find(mn[i]);
S.insert(pe[i]), S.erase(mx[i]);
d = query(S);
if(d > D) g[mx[i]] = 0, g[mn[i]] = 1;
if(d < D) g[mx[i]] = 1, g[mn[i]] = 0;
if(d == D) p[find(mx[i])] = find(mn[i]);
S.insert(mx[i]), S.erase(mn[i]);
}
// for(int i=0;i<M;i++) cout << g[i] << " \n"[i == M-1];
for(int i=0;i<M;i++) if(g[i] != -1) g[find(i)] = g[i];
// for(int i=0;i<M;i++) cout << g[i] << " \n"[i == M-1];
for(int i=0;i<M;i++) g[i] = g[find(i)];
// for(int i=0;i<M;i++) cout << g[i] << " \n"[i == M-1];
// for(int i=1;i<N;i++) cout << i << "/" << g[pe[i]] << " \n"[i == N-1];
for(int i=0;i<M;i++) if(g[i] == -1) g[i] = 0;
vector<int> re;
for(int i=0;i<M;i++) if(g[i]) re.push_back(i);
for(int i=0;i<M;i++) if(!t[i] && !g[i]) {
int x = in[a[i]] > in[b[i]] ? a[i] : b[i];
S.erase(pe[x]), S.insert(i);
if(D-g[pe[x]] < query(S)) re.push_back(i);
S.insert(pe[x]), S.erase(i);
}
return re;
}
