#include "fun.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
// int H = hoursRequired(0, N - 1);
// int A = attractionsBehind(0, N - 1);
vector<int> createFunTour(int N, int Q) {
int centroid = 0, subsiz = N;
for (int i = 1; i < N; i++) {
int csubsiz = attractionsBehind(0, i);
if (csubsiz > N / 2 && csubsiz < subsiz)
centroid = i, subsiz = csubsiz;
}
vector<int> depth(N);
for (int i = 0; i < N; i++)
depth[i] = i == centroid ? 0 : hoursRequired(centroid, i);
vector<int> g, type(N, 0);
for (int i = 0; i < N; i++)
if (depth[i] == 1) {
g.push_back(i);
}
const int M = g.size();
for (int i = 0; i < N; i++) if (i != centroid) {
for (int j = 1; j < M; j++) {
if (hoursRequired(g[j], i) == depth[i] - 1) {
type[i] = j; break;
}
}
}
cout << centroid << '\n';
cout << M << '\n';
for (int i = 0; i < N; i++) {
cout << depth[i] << ' ' << type[i] << '\n';
}
vector<int> res;
vector<pair<int, int>> group[M];
for (int i = 0; i < N; i++) if (i != centroid)
group[type[i]].emplace_back(depth[i], i);
for (int i = 0; i < M; i++)
sort(group[i].begin(), group[i].end());
for (int turn = N - 1, f = -1; turn --; ) {
int p = -1, c = -1;
for (int i = 0; i < M; i++) {
if (i != f && (int) group[i].size() > c)
p = i, c = group[i].size();
}
assert(c > 0);
res.push_back(group[p].back().second);
group[p].pop_back(), f = p;
}
res.push_back(centroid);
return res;
}
