#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) v.begin(),v.end()
vint find_roads(int n, vint u, vint v) {
int m = u.size();
vector<vpii> e(n);
for(int i = 0; i < m; i++) {
e[u[i]].emplace_back(v[i], i);
e[v[i]].emplace_back(u[i], i);
}
vint ord(n), low(n), tv;
vpii par(n);
vector<vpii> te(n), be(n);
function<void(int, int)> f = [&](int x, int y) {
static int cnt = 0;
ord[x] = low[x] = ++cnt;
for(pii &p : e[x]) {
if(y == p.x) par[x] = p;
else if(!ord[p.x]) {
f(p.x, x);
te[x].push_back(p);
tv.push_back(p.y);
low[x] = min(low[x], low[p.x]);
}
else if(ord[x] > ord[p.x]) {
be[x].push_back(p);
low[x] = min(low[x], ord[p.x]);
}
}
};
f(0, 0);
auto rep1 = [&](int x, int y) {
vint v = tv;
*find(all(v), x) = y;
return v;
};
int T = count_common_roads(tv);
vint ans(m, -1);
function<void(int)> g = [&](int x) {
for(pii &p : te[x]) g(p.x);
if(x && low[x] == ord[x]) {
ans[par[x].y] = 1;
return;
}
if(be[x].empty()) return;
sort(all(be[x]), [&](pii &p, pii &q) {
return ord[p.x] > ord[q.x];
});
pii B = be[x].back();
if(ans[par[x].y] >= 0) {
ans[B.y] = count_common_roads(rep1(par[x].y, B.y)) - T + ans[par[x].y];
for(int t = par[x].x; t != B.x; t = par[t].x) {
if(ans[par[t].y] < 0)
ans[par[t].y] = T - count_common_roads(rep1(par[t].y, B.y)) + ans[B.y];
}
}
else {
int mn = 0, mx = 0;
for(int t = x; t != B.x; t = par[t].x) {
ans[par[t].y] = count_common_roads(rep1(par[t].y, B.y)) - T;
mn = min(mn, ans[par[t].y]);
mx = max(mx, ans[par[t].y]);
}
ans[B.y] = mx;
if(mn < mx) {
for(int t = x; t != B.x; t = par[t].x) ans[par[t].y] = mx - ans[par[t].y];
}
}
be[x].pop_back();
};
g(0);
vint chk(m), val(m);
int ts = 0;
function<void(vint&, vint&, int, int, int)> h =
[&](vint &v, vint &w, int s, int e, int c) {
if(c == 0 || c == e - s + 1) {
for(int i = s; i <= e; i++) ans[v[i]] = !!c;
return;
}
ts++;
int m = (s + e) / 2;
for(int i = s; i <= m; i++) {
chk[w[i]] = ts;
val[w[i]] = v[i];
}
vint cv = tv;
int ofs = 0;
for(int &x : cv) if(chk[x] == ts) {
ofs += ans[x];
x = val[x];
}
int lc = count_common_roads(cv) - T + ofs;
h(v, w, s, m, lc);
h(v, w, m + 1, e, c - lc);
};
for(int x = 1; x < n; x++) {
if(be[x].empty()) continue;
vint v, w;
int sz = be[x].size();
for(int i = 0, t = x; i < sz; i++) {
v.push_back(be[x][i].y);
w.push_back(par[t].y);
t = be[x][i].x;
}
ts++;
for(int i = 0; i < sz; i++) {
chk[w[i]] = ts;
val[w[i]] = v[i];
}
vint cv = tv;
int ofs = 0;
for(int &y : cv) if(chk[y] == ts) {
ofs += ans[y];
y = val[y];
}
h(v, w, 0, sz - 1, count_common_roads(cv) - T + ofs);
}
vint ret;
for(int i = 0; i < m; i++) if(ans[i]) ret.push_back(i);
return ret;
}
