#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTour(int N, int Q) {
//int H = hoursRequired(0, N - 1);
//int A = attractionsBehind(0, N - 1);
//return std::vector<int>(N);
if (N == 2) {
return {0, 1};
}
vector<int> subtrees(N);
subtrees[0] = N-1;
for (int i = 1; i < N; i++) {
subtrees[i] = attractionsBehind(0, i);
}
int temp = 0;
for (int i = 1; i < N; i++) {
if (subtrees[temp] > subtrees[i] and subtrees[i] >= (N+1)/2) {
temp = i;
}
}
int r = temp;
cout << subtrees[0] << " " << subtrees[1] << " " << subtrees[2] << " " << r << "\n";
vector<pair<int, int>> dists;
for (int i = 0; i < N; i++) {
if (i == r) {
continue;
}
dists.push_back({hoursRequired(r, i), i});
}
sort(dists.begin(), dists.end());
vector<pair<int, int>> a, b, c;
a.push_back({1, dists[0].second});
b.push_back({1, dists[1].second});
for (int i = 2; i < N-1; i++) {
if (hoursRequired(dists[i].second, a[0].second) == dists[i].first-1) {
a.push_back(dists[i]);
//cout << "a: " << dists[i].first << dists[i].second << "\n";
} else if (hoursRequired(dists[i].second, b[0].second) == dists[i].first-1) {
b.push_back(dists[i]);
//cout << "b: " << dists[i].first << dists[i].second << "\n";
} else {
c.push_back(dists[i]);
//cout << "c: " << dists[i].first << dists[i].second << "\n";
}
}
vector<int> ans;
int branch = 0;
if (!c.empty()) {
while (c.size() + b.size() != a.size() and a.size() + c.size() != b.size() and a.size() + b.size() != c.size()) {
if (branch == 0) {
if (a.back().first >= b.back().first and a.back().first >= c.back().first) {
branch = 1;
ans.push_back(a.back().second);
a.pop_back();
} else if (b.back().first >= c.back().first and b.back().first >= a.back().first) {
branch = 2;
ans.push_back(b.back().second);
b.pop_back();
} else {
branch = 3;
ans.push_back(c.back().second);
c.pop_back();
}
} else if (branch == 1) {
if (b.back().first >= c.back().first) {
branch = 2;
ans.push_back(b.back().second);
b.pop_back();
} else {
branch = 3;
ans.push_back(c.back().second);
c.pop_back();
}
} else if (branch == 2) {
if (a.back().first >= c.back().first) {
branch = 1;
ans.push_back(a.back().second);
a.pop_back();
} else {
branch = 3;
ans.push_back(c.back().second);
c.pop_back();
}
} else if (branch == 3) {
if (a.back().first >= b.back().first) {
branch = 1;
ans.push_back(a.back().second);
a.pop_back();
} else {
branch = 2;
ans.push_back(b.back().second);
b.pop_back();
}
}
}
if (a.size() == b.size() + c.size()) {
for (auto i:c) {
b.push_back(i);
}
sort(b.begin(), b.end());
if (branch == 3) {
branch = 2;
}
} else if (b.size() == a.size() + c.size()) {
for (auto i:c) {
a.push_back(i);
}
sort(a.begin(), a.end());
if (branch == 3) {
branch = 2;
}
} else {
for (auto i:a) {
b.push_back(i);
}
sort(b.begin(), b.end());
a = c;
if (branch == 1) {
branch = 2;
}
if (branch == 3) {
branch = 1;
}
}
}
if (branch == 0) {
if (a.size() < b.size()) {
branch = 1;
} else {
branch = 2;
}
}
while (!a.empty() or !b.empty()) {
if (branch == 1) {
branch = 2;
ans.push_back(b.back().second);
b.pop_back();
} else {
branch = 1;
ans.push_back(a.back().second);
a.pop_back();
}
}
/*cout << "final\n";
for (auto i:ans) {
cout << i << " ";
}
cout << "\n";*/
ans.push_back(r);
return ans;
}
