#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
void setDsu(vector<int> &dsu, vector<int> &sz) {
int n = dsu.size();
for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1;
}
int findHead(vector<int> &dsu, int node) {
if (node == dsu[node]) return node;
return dsu[node] = findHead(dsu, dsu[node]);
}
bool merge(vector<int> &dsu, vector<int> &sz, int a, int b) {
a = findHead(dsu, a);
b = findHead(dsu, b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
dsu[b] = a;
sz[a] += sz[b];
return true;
}
void dfs(vector<vector<pair<int, int>>> &adjacency, vector<int> &dfsSequence, vector<int> &parent, vector<bool> &dfsVisited, int curNode) {
for (auto &[i, index] : adjacency[curNode]) {
if (dfsVisited[i]) continue;
dfsVisited[i] = true;
dfsSequence.push_back(i);
parent[i] = curNode;
dfs(adjacency, dfsSequence, parent, dfsVisited, i);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
if (n == 2) return {0};
int m = u.size();
vector<vector<pair<int, int>>> adjacency(n);
vector<vector<int>> adjacencyMatrix(n, vector<int>(n, -1));
for (int i = 0; i < m; ++i) {
adjacency[u[i]].emplace_back(v[i], i);
adjacency[v[i]].emplace_back(u[i], i);
adjacencyMatrix[u[i]][v[i]] = i;
adjacencyMatrix[v[i]][u[i]] = i;
}
// cout << "Find roads Begins" << endl;
vector<pair<int, int>> t;
vector<bool> dfsVisited(n, false), tCounted(n, false);
dfsVisited[0] = true;
vector<int> parent(n, -1), dfsSequence{0};
vector<vector<int>> ears;
dfs(adjacency, dfsSequence, parent, dfsVisited, 0);
// cout << "DFS complete" << endl;
vector<int> dsu(n), sz(n);
vector<vector<int>> inTree(n, vector<int>(n, -1));
setDsu(dsu, sz);
// cout << "Sequence: ";
// for (int &i : dfsSequence) cout << i << ' ';
// cout << endl;
vector<vector<bool>> processed(n, vector<bool>(n, false));
for (int &_u : dfsSequence) {
for (auto &[_v, index] : adjacency[_u]) {
if (parent[_u] == _v || parent[_v] == _u || processed[_u][_v]) continue;
vector<int> ear;
bool add = false;
ear.push_back(_u);
// if (!tCounted[u]) add = true, tCounted[u] = true;
// cout << _u << ' ' << _v << endl;
for (int x = _v; ; x = parent[x]) {
if (x == ear[0]) break;
ear.push_back(x);
if (merge(dsu, sz, x, parent[x])) inTree[x][parent[x]] = t.size(), inTree[parent[x]][x] = t.size(), t.emplace_back(x, parent[x]), add = true;
// if (!tCounted[x]) add = true;
// tCounted[x] = true;
}
// for (int &i : ear) cout << i << ' ';
// cout << "add: " << add << endl;
if (add) ears.push_back(ear);
processed[_u][_v] = true;
processed[_v][_u] = true;
// cout << _u << ' ' << _v << ' ' << add << endl;
}
}
vector<int> edgeStates(m, -1); // -1 = unknown, 0 = not golden, 1 = golden
vector<int> res;
vector<int> tWeight(n - 1, 0);
vector<vector<bool>> goldTree(n, vector<bool>(n, false));
vector<int> sub(n, 0);
// cout << "t: " << t.size() << endl;
// for (auto &i : t) cout << i.first << ' ' << i.second << " ";
// cout << endl;
for (int i = 0; i < m; ++i) {
if (merge(dsu, sz, u[i], v[i])) {
inTree[u[i]][v[i]] = t.size();
inTree[v[i]][u[i]] = t.size();
t.emplace_back(u[i], v[i]);
int which = t.size() - 1;
tWeight[which] = 1;
res.push_back(adjacencyMatrix[t[which].first][t[which].second]);
++sub[t[which].first];
++sub[t[which].second];
goldTree[t[which].first][t[which].second] = true;
goldTree[t[which].second][t[which].first] = true;
}
}
// cout << "t: " << t.size() << endl;
// for (auto &i : t) cout << i.first << ' ' << i.second << " ";
// cout << endl;
// cout << "res: " << res.size() << endl;
// for (auto &i : res) cout << u[i] << ' ' << v[i] << " ";
// cout << endl;
assert(t.size() == n - 1);
// cout << "Tree chosen" << endl;
for (auto &ear : ears) {
int earSz = ear.size();
int known = -1;
bool knownIs = false;
vector<pair<int, int>> curCycle;
for (int i = 0; i < earSz - 1; ++i) curCycle.emplace_back(ear[i], ear[i + 1]);
if (earSz > 2) curCycle.emplace_back(ear[earSz - 1], ear[0]);
int cycleSz = curCycle.size();
for (int i = 0; i < cycleSz; ++i) {
if (edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] != -1) {
known = i;
knownIs = edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]];
break;
}
}
vector<int> records(cycleSz, -1);
int sample = 0;
for (int i = 0; i < cycleSz; ++i) {
if (known != -1 && (inTree[curCycle[i].first][curCycle[i].second] == -1 || edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] != -1) && i != known) continue;
++sample;
vector<int> r;
setDsu(dsu, sz);
// cout << "NEW" << endl;
for (int j = 0; j < cycleSz; ++j) {
// cout << curCycle[j].first << ' ' << curCycle[j].second << endl;
if (i == j) continue;
assert(merge(dsu, sz, curCycle[j].first, curCycle[j].second));
r.push_back(adjacencyMatrix[curCycle[j].first][curCycle[j].second]);
}
for (auto &[a, b] : t) {
if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b]);
}
assert(r.size() == n - 1);
records[i] = count_common_roads(r);
}
if (sample < 2) continue;
if (known == -1) {
int least = records[0], most = records[0];
for (int &j : records) {
if (j == -1) continue;
least = min(least, j), most = max(most, j);
}
for (int i = 0; i < cycleSz; ++i) {
if (records[i] == -1) continue;
if (records[i] != most) {
edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 1;
if (inTree[curCycle[i].first][curCycle[i].second] != -1) {
int which = inTree[curCycle[i].first][curCycle[i].second];
tWeight[which] = 1;
res.push_back(adjacencyMatrix[t[which].first][t[which].second]);
++sub[t[which].first];
++sub[t[which].second];
goldTree[t[which].first][t[which].second] = true;
goldTree[t[which].second][t[which].first] = true;
}
// cout << "FOUND GOLD EDGE(Unknown): " << i << ' ' << curCycle[i].first << ' ' << curCycle[i].second << '\n';
} else edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 0;
}
} else {
for (int i = 0; i < cycleSz; ++i) {
if (records[i] == -1 || i == known) continue;
if ((records[i] == records[known] && knownIs) || (records[i] != records[known] && !knownIs)) {
edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 1;
if (inTree[curCycle[i].first][curCycle[i].second] != -1) {
int which = inTree[curCycle[i].first][curCycle[i].second];
tWeight[which] = 1;
res.push_back(adjacencyMatrix[curCycle[i].first][curCycle[i].second]);
++sub[t[which].first];
++sub[t[which].second];
goldTree[t[which].first][t[which].second] = true;
goldTree[t[which].second][t[which].first] = true;
}
// cout << "FOUND GOLD EDGE(Known): " << i << ' ' << curCycle[i].first << ' ' << curCycle[i].second << '\n';
// cout << "KNOWN EDGE IS: " << known << ' ' << curCycle[known].first << ' ' << curCycle[known].second << ' ' << knownIs << '\n';
} else edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 0;
}
}
// for (int &i : ear) cout << i << ' ';
// cout << endl;
// for (int i = 0; i < m; ++i) cout << u[i] << ' ' << v[i] << ' ' << edgeStates[i] << " ";
// cout << endl;
}
// cout << "res: " << res.size() << endl;
// for (auto &i : res) cout << u[i] << ' ' << v[i] << " ";
// cout << endl;
// cout << "Edges of Tree done" << endl;
/*
// vector<int> res;
// vector<int> tWeight(n - 1, 0);
// vector<vector<bool>> goldTree(n, vector<bool>(n, false));
// vector<int> sub(n, 0);
// for (int i = 0; i < n - 1; ++i) {
// vector<pair<int, int>> curCycle = {t[i]};
// int other = 0;
// if (t[i].first == 0 || t[i].second == 0) {
// other = 1;
// if (t[i].first == 1 || t[i].second == 1) other = 2;
// }
// curCycle.emplace_back(t[i].first, other);
// curCycle.emplace_back(t[i].second, other);
// vector<int> scores;
// for (int j = 0; j < 3; ++j) {
// vector<int> r;
// setDsu(dsu, sz);
// for (int k = 0; k < 3; ++k) {
// if (j == k) continue;
// assert(merge(dsu, sz, curCycle[k].first, curCycle[k].second));
// r.push_back(adjacencyMatrix[curCycle[k].first][curCycle[k].second]);
// }
// for (auto &[a, b] : t) {
// if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b]);
// }
// assert(r.size() == n - 1);
// scores.push_back(count_common_roads(r));
// }
// int least = scores[0], most = scores[0];
// for (int &j : scores) least = min(least, j), most = max(most, j);
// if (scores[0] != most) {
// tWeight[i] = 1;
// res.push_back(adjacencyMatrix[t[i].first][t[i].second]);
// ++sub[t[i].first];
// ++sub[t[i].second];
// goldTree[t[i].first][t[i].second] = true;
// goldTree[t[i].second][t[i].first] = true;
// }
// }
*/
// Done:
vector<int> nodeWeights(n, -1);
for (int node = 0; node < n; ++node) {
setDsu(dsu, sz);
vector<int> r;
for (auto &[adjacent, index] : adjacency[node]) {
assert(merge(dsu, sz, node, adjacent));
r.push_back(index);
}
int base = 0;
for (int i = 0; i < n - 1; ++i) {
if (merge(dsu, sz, t[i].first, t[i].second)) {
r.push_back(adjacencyMatrix[t[i].first][t[i].second]);
base += tWeight[i];
}
}
assert(r.size() == n - 1);
nodeWeights[node] = count_common_roads(r) - base;
}
// int cnt = 0;
while (res.size() != n - 1) {
// if (++cnt > 100) break;
// cout << cnt << ' ' << res.size() << endl;
// for (int &i : res) cout << i << ' ';
// cout << endl;
for (int node = 0; node < n; ++node) {
if (nodeWeights[node] - sub[node] != 1) continue;
int low = 0, high = adjacency[node].size() - sub[node];
while (low < high - 1) {
int mid = (low + high) / 2;
setDsu(dsu, sz);
vector<int> r;
int shift = 0;
for (int i = 0; i < mid; ++i) {
if (goldTree[node][adjacency[node][i + shift].first]) {
--i; ++shift;
continue;
}
assert(merge(dsu, sz, node, adjacency[node][i + shift].first));
r.push_back(adjacency[node][i + shift].second);
}
int base = 0;
for (int i = 0; i < n - 1; ++i) {
if (merge(dsu, sz, t[i].first, t[i].second)) {
r.push_back(adjacencyMatrix[t[i].first][t[i].second]);
base += tWeight[i];
}
}
assert(r.size() == n - 1);
if (count_common_roads(r) - base) high = mid;
else low = mid;
}
int shift = 0;
for (int i = 0; i <= low; ++i) {
if (goldTree[node][adjacency[node][i + shift].first]) {
--i; ++shift;
continue;
}
}
shift += low;
res.push_back(adjacency[node][shift].second);
++sub[node];
++sub[adjacency[node][shift].first];
goldTree[node][adjacency[node][shift].first] = true;
goldTree[adjacency[node][shift].first][node] = true;
}
}
return res;
}
