#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = (int) u.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
dsu d(n);
vector<int> tree;
for (int i = 0; i < m; i++) {
if (d.unite(u[i], v[i])) {
tree.push_back(i);
}
}
vector<vector<int>> t(n);
for (int i : tree) {
t[u[i]].push_back(i);
t[v[i]].push_back(i);
}
int cnt = count_common_roads(tree);
const int L = 20;
vector<vector<int>> pr(n, vector<int>(L));
vector<int> dep(n);
vector<int> id(n);
function<void(int, int)> Dfs = [&](int x, int px) {
dep[x] = dep[px] + 1;
pr[x][0] = px;
for (int i = 1; i < L; i++) {
pr[x][i] = pr[pr[x][i - 1]][i - 1];
}
for (int e : t[x]) {
int y = (x ^ u[e] ^ v[e]);
if (y == px) {
continue;
}
id[y] = e;
Dfs(y, x);
}
};
Dfs(0, 0);
auto LCA = [&](int x, int y) {
if (dep[x] > dep[y]) {
swap(x, y);
}
for (int i = L - 1; i >= 0; i--) {
if (dep[pr[y][i]] >= dep[x]) {
y = pr[y][i];
}
}
if (x == y) {
return x;
}
for (int i = L - 1; i >= 0; i--) {
if (pr[x][i] != pr[y][i]) {
x = pr[x][i];
y = pr[y][i];
}
}
return pr[x][0];
};
vector<int> state(m, 2);
for (int i : tree) {
state[i] = -1;
}
for (int i = 0; i < m; i++) {
if (state[i] != 2) {
continue;
}
vector<int> edges;
int z = LCA(u[i], v[i]);
for (int x = u[i]; x != z; x = pr[x][0]) {
edges.push_back(id[x]);
}
for (int x = v[i]; x != z; x = pr[x][0]) {
edges.push_back(id[x]);
}
vector<pair<int, int>> a;
for (int e : edges) {
if (state[e] != -1) {
continue;
}
vector<int> qv(1, i);
for (int i : tree) {
if (i != e) {
qv.push_back(i);
}
}
a.emplace_back(count_common_roads(qv), e);
}
if (a.empty()) {
continue;
}
for (auto& p : a) {
if (p.first == cnt - 1) {
state[i] = 0;
}
if (p.first == cnt + 1) {
state[i] = 1;
}
}
if (state[i] == 2) {
for (int e : edges) {
if (state[e] == -1) {
continue;
}
vector<int> qv(1, i);
for (int i : tree) {
if (i != e) {
qv.push_back(i);
}
}
state[i] = (state[e] ^ (cnt != count_common_roads(qv) ? 1 : 0));
break;
}
if (state[i] == 2) {
state[i] = 0;
}
}
for (auto& p : a) {
state[p.second] = (state[i] ^ (cnt != p.first ? 1 : 0));
}
}
for (int e : tree) {
if (state[e] == -1) {
state[e] = 1;
}
}
vector<int> deg(n);
for (int i = 0; i < n; i++) {
dsu d(n);
vector<int> qv;
for (int e : g[i]) {
qv.push_back(e);
d.unite(u[e], v[e]);
}
int ft = 0;
for (int e : tree) {
if (d.unite(u[e], v[e])) {
qv.push_back(e);
ft += state[e];
}
}
deg[i] = count_common_roads(qv) - ft;
}
vector<int> que;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) {
que.push_back(i);
}
}
vector<bool> was(n);
vector<int> res;
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
if (i == 0) {
continue;
}
was[i] = true;
vector<int> f;
for (int e : g[i]) {
if (!was[u[e] ^ v[e] ^ i]) {
f.push_back(e);
}
}
int low = 0, high = (int) f.size() - 1, who = -1;
while (low <= high) {
int mid = (low + high) >> 1;
vector<int> qv;
dsu d(n);
for (int j = 0; j <= mid; j++) {
qv.push_back(f[j]);
d.unite(u[f[j]], v[f[j]]);
}
int ft = 0;
for (int e : tree) {
if (d.unite(u[e], v[e])) {
qv.push_back(e);
ft += state[e];
}
}
if (count_common_roads(qv) - ft > 0) {
who = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
res.push_back(f[who]);
int j = (u[f[who]] ^ v[f[who]] ^ i);
deg[j] -= 1;
if (deg[j] == 1) {
que.push_back(j);
}
}
return res;
}
