#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;
int ori;
vector<vector<pii>> adj;
vector<vector<pii>> back_edges;
vector<vector<pii>> childs;
vector<int> color; // -1 : uncolored, 0 : normal edge, 1 : golden edge
vector<int> vis;
vector<pii> par;
vector<int> dep;
vector<int> query;
vector<int> ans;
int ask() { return count_common_roads(query); }
void ins(vector<int> v) {
for (auto &i : v)
query.push_back(i);
}
vector<int> chk;
void del(vector<int> v) {
for (auto &i : v) chk[i] = 1;
vector<int> t;
for (auto &i : query)
if (!chk[i])
t.push_back(i);
query = t;
for (auto &i : v) chk[i] = 0;
}
void make_dfs_tree(int x) {
vis[x] = 1;
for (auto &[y, id] : adj[x]) {
if (y == par[x].first) continue;
if (vis[y]) {
back_edges[x].emplace_back(y, id);
continue;
}
}
for (auto &[y, id] : adj[x]) {
if (vis[y]) continue;
childs[x].emplace_back(y, id);
par[y] = make_pair(x, id);
dep[y] = dep[x] + 1;
make_dfs_tree(y);
}
}
void color_dfs_tree(int x) {
if (!back_edges.empty()) {
int mn = inf;
pii e;
for (auto &[y, id] : back_edges[x]) {
if (mn > dep[y]) {
mn = dep[y];
e = make_pair(y, id);
}
}
if (mn < inf) {
vector<int> path;
int t = x;
int oth = -1;
while (t != e.first) {
if (color[par[t].second] == -1)
path.push_back(par[t].second);
else
oth = par[t].second;
t = par[t].first;
}
vector<int> ret(path.size());
ins({e.second});
for (int i=0; i<(int)path.size(); i++) {
del({path[i]});
ret[i] = ask();
ins({path[i]});
}
del({e.second});
int d = 0;
if (oth == -1) {
for (int i=0; i<(int)path.size(); i++) {
if (ret[i] > ori) d = 1;
}
}
else {
ins({e.second});
del({oth});
d = ask() > ori-color[oth] ? 1 : 0;
del({e.second});
ins({oth});
}
for (int i=0; i<(int)path.size(); i++) {
color[path[i]] = ret[i]-d < ori ? 1 : 0;
}
}
}
for (auto &[y, id] : childs[x]) {
color_dfs_tree(y);
}
}
void color_back_edges(int x) {
if (!back_edges.empty()) {
sort(back_edges[x].begin(), back_edges[x].end(), [&] (pii u, pii v) { return dep[u.first] > dep[v.first]; });
vector<int> er(back_edges[x].size());
int idx = 0;
int t = x;
while (t > 0) {
if (idx < (int)back_edges[x].size() && par[t].first == back_edges[x][idx].first) {
er[idx] = par[t].second;
idx ++;
}
t = par[t].first;
}
int p = 0;
while (true) {
int lo = p, hi = (int)back_edges[x].size();
while (lo < hi) {
int mid = lo + hi >> 1;
int d = 0;
vector<int> t1, t2;
for (int i=p; i<=mid; i++) {
t1.push_back(back_edges[x][i].second);
t2.push_back(er[i]);
d += color[er[i]];
}
ins(t1);
del(t2);
if (ori - d < ask()) hi = mid;
else lo = mid + 1;
del(t1);
ins(t2);
}
if (lo == (int)back_edges[x].size()) break;
ans.push_back(back_edges[x][lo].second);
p = lo + 1;
}
}
for (auto &[y, id] : childs[x]) {
color_back_edges(y);
}
}
void init(int n, int m) {
adj.resize(n, vector<pii>());
back_edges.resize(n, vector<pii>());
childs.resize(n, vector<pii>());
color.resize(m, -1);
vis.resize(n, 0);
par.resize(n);
dep.resize(n);
chk.resize(m, 0);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = (int) u.size();
init(n, m);
for (int i=0; i<m; i++) {
adj[u[i]].emplace_back(v[i], i);
adj[v[i]].emplace_back(u[i], i);
}
par[0] = make_pair(-1,-1);
dep[0] = 0;
make_dfs_tree(0);
for (int i=1; i<n; i++) query.push_back(par[i].second);
ori = ask();
color_dfs_tree(0);
for (int i=1; i<n; i++) {
if (color[par[i].second] == -1) color[par[i].second] = 0;
else if (color[par[i].second] == 1) ans.push_back(par[i].second);
}
color_back_edges(0);
return ans;
}
