#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, D, 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()));
}
int query(set<int> S, vector<int> L) {
int p = 0;
for(auto id : L) {
int x = pe[in[a[id]] > in[b[id]] ? a[id] : b[id]];
p += g[x], S.erase(x), S.insert(id);
}
return query(S) - (D-p);
}
void solve(int l, int r, int s, const set<int> &S, const vector<int> &L) {
if(!s) return;
if(l == r) {
g[L[l]] = 1;
return;
}
int mid = (l+r) >> 1;
int ls = query(S, vector<int>(L.begin()+l, L.begin()+mid+1));
solve(l, mid, ls, S, L);
solve(mid+1, r, s-ls, S, L);
}
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]);
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;
}
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++) if(g[i] != -1) g[find(i)] = g[i];
for(int i=0;i<M;i++) g[i] = g[find(i)];
for(int i=0;i<M;i++) if(g[i] == -1) g[i] = 0;
for(int i=0;i<N;i++) {
vector<int> L;
for(auto x : v[i]) if(!g[x] && in[i] < in[a[x]^b[x]^i]) L.push_back(x);
if(!L.empty()) solve(0, L.size()-1, query(S, L), S, L);
}
vector<int> re;
for(int i=0;i<M;i++) if(g[i]) re.push_back(i);
return re;
}
