//Challenge: Accepted
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int tot;
int dis[18][maxn], dep[maxn], outsiz[18][maxn];
int getsize(int u, int v) {
for (int i = 17;i >= 0;i--) {
if (dis[i][u] > dis[i][v]) return attractionsBehind(u, v) - outsiz[i][u];
}
return attractionsBehind(u, v);
}
int recur[maxn];
void solve(vector<int> v, int d) {
//debug("solve");
//pary(v.begin(), v.end());
if (v.size() == 1) {
dep[v[0]] = d;
return;
}
int root = v[0], siz = v.size();
for (int i = 1;i < v.size();i++) {
if (getsize(root, v[i]) * 2 > siz) {
root = v[i];
}
}
dep[root] = d;
vector<int> con;
for (int i:v) {
if (i == root) continue;
recur[i] = 0;
dis[d][i] = hoursRequired(root, i);
if (dis[d][i] == 1) {
adj[root].push_back(i);
adj[i].push_back(root);
con.push_back(i);
}
}
for (int i = 1;i < con.size();i++) {
for (int j:v) {
if (j != root && !recur[j]) {
if (getsize(j, con[i]) * 2 > siz) {
recur[j] = i;
}
}
}
}
vector<vector<int> > rec;
for (int i = 0;i < con.size();i++) {
vector<int> tmp;
int p = getsize(con[i], root);
for (int j:v) {
if (j != root && recur[j] == i) {
outsiz[j][d] = p;
tmp.push_back(j);
}
}
rec.push_back(tmp);
}
for (auto i:rec) solve(i, d+1);
}
bool vis[maxn];
pii dfs(int n, int pa, int d) {
pii ret = {d, n};
for (int v:adj[n]) {
if (v != pa && !vis[v]) {
ret = max(ret, dfs(v, n, d + 1));
}
}
return ret;
}
vector<int> createFunTour(int N, int Q) {
tot = N;
int H = hoursRequired(0, N - 1);
int A = attractionsBehind(0, N - 1);
vector<int> ini, ret;
for (int i = 0;i < N;i++) ini.push_back(i);
solve(ini, 0);
int st = max_element(dis[0], dis[0] + N) - dis[0];
for (int i = 0;i < N;i++) {
vis[st] = 1;
ret.push_back(st);
int nxt = dfs(st, -1, 0).ss;
st = nxt;
}
/*
for (int i = 0;i < N;i++) {
debug(i);
pary(adj[i].begin(), adj[i].end());
}
pary(ret.begin(), ret.end());
*/
return ret;
}
