// You can't change other people; you can only change yourself.
#include "fun.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
// Data types
using i8 = __int128;
using ll = long long;
using si = short int;
using ld = long double;
// Pairs
using pi8 = pair<i8, i8>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using psi = pair<si, si>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
// Constants
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
vector<int> createFunTour(int N, int Q) {
// corner case
if (N == 2) {return {0, 1};}
// Find centroid of tree
int minSubtree = iINF, centroid = -1;
int _0 = attractionsBehind(1, 0);
if (_0 >= (N+1)/2) {
minSubtree = _0;
centroid = 0;
}
for (int i = 1; i < N; i++) {
int cur = attractionsBehind(0, i);
if (cur >= (N+1)/2 && cur < minSubtree) {
centroid = i;
minSubtree = cur;
}
}
//printf("Centroid: %d\n", centroid);
// Find distance of all nodes to centroid
// Also find the 'groups' of nodes from centroid
vector<int> groupRep, groupRepSize;
vector<vector<pii>> groups;
vector<int> dist(N);
for (int i = 0; i < N; i++) {
if (i == centroid) continue;
dist[i] = hoursRequired(centroid, i);
if (dist[i] == 1) {
groupRep.push_back(i);
groups.push_back({{1, i}});
}
}
for (auto i : groupRep) {
groupRepSize.push_back(attractionsBehind(centroid, i));
}
assert(groupRep.size() > 1);
//for (auto i : dist) cout << i << ' '; cout << '\n';
//for (auto i : groupRep) cout << i << ' '; cout << '\n';
//for (auto i : groupRepSize) cout << i << ' '; cout << '\n';
// Find which group each node belongs to
for (int i = 0; i < N; i++) {
if (dist[i] <= 1) continue;
bool found = 0;
for (int g = 0; g < groupRep.size()-1; g++) {
//printf("Checking %d in group %d\n", i, groupRep[g]);
if (hoursRequired(i, groupRep[g]) == dist[i] - 1) {
groups[g].push_back({dist[i], i});
found = 1;
break;
}
}
if (!found) {
groups.back().push_back({dist[i], i});
}
}
for (auto &g : groups) {
sort(g.begin(), g.end());
//for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
}
// construct fun tour!
vector<int> ans;
int lastPicked = -1;
for (int i = 1; i < N; i++) {
//printf("Last picked %d\n", lastPicked);
//for (auto g : groups) {
// for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
//}
if (groups.size() == 3) {
int mx = -1, mxIndex = -1;
for (int g = 0; g < 3; g++) {
if (g == lastPicked) continue;
if (groups[g].back().fi > mx) {
mx = groups[g].back().fi;
mxIndex = g;
}
}
ans.push_back(groups[mxIndex].back().se);
groups[mxIndex].pop_back();
lastPicked = mxIndex;
int sz[] = {(int)groups[0].size(), (int)groups[1].size(), (int)groups[2].size()};
bool merge = 0;
if (sz[0] + sz[1] == sz[2]) {
merge = 1;
swap(groups[0], groups[2]);
if (lastPicked == 0) {lastPicked = 1;}
else if (lastPicked == 2) {lastPicked = 0;}
} else if (sz[0] + sz[2] == sz[1]) {
merge = 1;
swap(groups[0], groups[1]);
if (lastPicked == 2) {lastPicked = 1;}
else if (lastPicked == 1) {lastPicked = 0;}
} else if (sz[1] + sz[2] == sz[0]) {
merge = 1;
if (lastPicked == 2) {lastPicked = 1;}
}
if (merge) {
for (auto x : groups[2]) {groups[1].push_back(x);}
groups.pop_back();
sort(groups.back().begin(), groups.back().end());
}
} else {
for (int g = 0; g < 2; g++) {
if (lastPicked == g) {continue;}
ans.push_back(groups[g].back().se);
groups[g].pop_back();
lastPicked = g;
break;
}
}
}
ans.push_back(centroid);
//for (auto i : ans) {cout << i << ' ';} cout << '\n';
return ans;
}
//int main() {}
