#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTourForSubtasks1and2(int n, int q) {
vector<vector<int>> g(n);
int cnt_edges = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
g[i].push_back(j);
g[j].push_back(i);
cnt_edges++;
}
}
}
assert(cnt_edges == n - 1);
vector<bool> active(n, 1);
vector<int> dist(n, -1);
function<int(int)> find_far = [&] (int root) {
assert(active[root]);
queue<int> q;
for (int i = 0; i < n; i++) {
dist[i] = -1;
}
dist[root] = 0;
q.push(root);
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto &b : g[a]) {
if (active[b] && dist[b] == -1) {
dist[b] = 1 + dist[a];
q.push(b);
}
}
}
int sol = root;
for (int i = 0; i < n; i++) {
if (dist[i] > dist[sol]) {
sol = i;
}
}
return sol;
};
vector<int> ord;
ord.push_back(find_far(0));
for (int step = 2; step <= n; step++) {
int nw = find_far(ord.back());
active[ord.back()] = 0;
ord.push_back(nw);
}
assert((int) ord.size() == n);
return ord;
}
vector<int> createFunTour(int n, int q) {
if (n == 2) {
return vector<int> {0, 1};
}
vector<vector<int>> g(n);
int cnt_edges = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
g[i].push_back(j);
g[j].push_back(i);
cnt_edges++;
}
}
}
assert(cnt_edges == n - 1);
vector<int> sub(n, 0), dist(n, 0);
function<void(int, int)> dfs = [&] (int a, int p) {
sub[a] = 1;
for (auto &b : g[a]) {
if (b == p) {
continue;
}
dist[b] = 1 + dist[a];
dfs(b, a);
sub[a] += sub[b];
}
};
dfs(0, -1);
assert(sub[0] == n);
function<int(int, int)> fcen = [&] (int a, int p) {
int mx = n - sub[a];
for (auto &b : g[a]) {
if (b == p) {
continue;
}
mx = max(mx, sub[b]);
}
if (mx <= n / 2) {
return a;
}
for (auto &b : g[a]) {
if (b == p) {
continue;
}
if (mx == sub[b]) {
return fcen(b, a);
}
}
assert(0);
};
int min_over = n;
for (int i = 0; i < n; i++) {
if (sub[i] >= n / 2 + 1) {
min_over = min(min_over, sub[i]);
}
}
int centroid = fcen(0, -1);
for (int i = 0; i < n; i++) {
assert((int) g[i].size() <= 3);
}
assert(centroid != -1);
vector<int> solution;
vector<int> arms = g[centroid];
vector<vector<pair<int, int>>> dists;
for (auto &v : arms) {
dists.push_back({});
function<void(int, int)> add_all_under = [&] (int a, int p) {
dists.back().push_back({dist[a], a});
for (auto &b : g[a]) {
if (b == p) {
continue;
}
add_all_under(b, a);
}
};
add_all_under(v, centroid);
}
for (auto &dist : dists) {
sort(dist.begin(), dist.end());
}
vector<int> sol;
int cur_id = -1;
for (int iter = 1; iter <= (int) dists.size(); iter++) {
for (int i = 0; i + 1 < (int) dists.size(); i++) {
if ((int) dists[i + 1].size() > (int) dists[i].size()) {
swap(dists[i], dists[i + 1]);
}
}
}
for (int step = 1; step <= n - 1; step++) {
int dim = (int) dists.size();
assert(dim == 2 || dim == 3);
if (step != 1) {
assert(0 <= cur_id && cur_id < dim);
}
int last = cur_id;
cur_id = -1;
for (int i = 0; i < dim; i++) {
if (last != i && !dists[i].empty()) {
cur_id = i;
}
}
assert(cur_id != -1);
for (int i = 0; i < dim; i++) {
if (last != i && !dists[i].empty()) {
if (dists[i].back().first > dists[cur_id].back().first) {
cur_id = i;
}
}
}
if (step == 1) {
cur_id = 0;
}
assert(0 <= cur_id && cur_id < dim);
{
int sld = 0;
for (auto &dist : dists) {
sld += (int) dist.size();
}
assert(sld + step == n);
}
assert(!dists[cur_id].empty());
if (dim == 3) {
for (int i = 0; i < 3; i++) {
int j = 0;
if (i == 0) {
j = 1;
}
int k = 3 - i - j;
if (cur_id == i) {
continue;
}
{ // very dumb check
set<int> s;
s.insert(i);
s.insert(j);
s.insert(k);
assert((int) s.size() == 3);
assert(s.count(0));
assert(s.count(1));
assert(s.count(2));
}
if ((int) dists[i].size() >= (int) dists[j].size() + (int) dists[k].size() - 1) {
vector<vector<pair<int, int>>> new_dists;
new_dists.push_back(dists[i]);
new_dists.push_back(dists[j]);
for (auto &it : dists[k]) {
new_dists.back().push_back(it);
}
sort(new_dists.back().begin(), new_dists.back().end());
dists = new_dists;
cur_id = 1;
dim = 2;
break;
}
}
}
if (0) {
cout << "lens = ";
for (auto &dist : dists) {
cout << (int) dist.size() << " ";
}
cout << ", cur_id = " << cur_id << "\n";
}
sol.push_back(dists[cur_id].back().second);
dists[cur_id].pop_back();
assert((int) dists.size() == dim);
}
sol.push_back(centroid);
if (0) {
for (auto &x : sol) {
cout << x << " ";
}
cout << "\n";
}
return sol;
}
