#include "fun.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n;
map<pair<int, int>, int> dst;
map<pair<int, int>, int> subtr;
int distance(int u, int v) {
if (u == v)
return 0;
if (dst.find({u, v}) != dst.end()) {
return dst[{u, v}];
}
if (dst.find({v, u}) != dst.end()) {
return dst[{v, u}];
}
return dst[{v, u}] = hoursRequired(u, v);
}
int subtree_size(int u, int v) {
if (u == v)
return n;
if (subtr.find({u, v}) != subtr.end()) {
return subtr[{u, v}];
}
return subtr[{u, v}] = attractionsBehind(u, v);
}
int find_maxdepth(int rt, vector<int> vs) {
int ans = rt;
int ansdepth = 0;
for (auto v : vs) {
int d = distance(rt, v);
if (d > ansdepth) {
ansdepth = d;
ans = v;
}
}
return ans;
}
vector<int> ans_dumb() {
vector<int> ans;
vector<int> vs(n);
for (int i = 0; i < n; ++i)
vs[i] = i;
int rt = find_maxdepth(0, vs);
ans.push_back(rt);
vs.erase(lower_bound(vs.begin(), vs.end(), rt));
while (vs.size()) {
int nv = find_maxdepth(rt, vs);
ans.push_back(nv);
rt = nv;
vs.erase(lower_bound(vs.begin(), vs.end(), nv));
}
return ans;
}
vector<int> createFunTour(int N, int Q) {
n = N;
if (n <= 500) {
return ans_dumb();
}
}
