#include "fun.h"
#pragma GCC optimize "O3,unroll-loops"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
using namespace std;
vector<int> tiers[200100];
int par[200100];
int lkx[200100];
bool zd;
set<pair<int,int>> mp[200100][4];
pair<int,int> furthest(int node){
pair<int,int> ans={-1,node};
for(auto i:mp[node])if(i.size())ans=max(ans,*i.rbegin());
int cur=node;
int dst=0;
while(cur){
auto pxt=par[cur];
++dst;
REP(i,0,3)if(i!=lkx[cur] && mp[pxt][i].size())ans=max(ans,{mp[pxt][i].rbegin()->fi + dst, mp[pxt][i].rbegin()->se});
cur=pxt;
}
if(!zd)ans=max(ans,{dst,0});
// cerr<<"FURTHEST FROM "<<node<<": "<<ans.se<<" (DISTANCE: "<<ans.fi<<")\n";
return ans;
}
std::vector<int> createFunTour(int N, int Q) {
memset(par,-1,sizeof par);
REP(i,0,N+10)tiers[i].clear(),mp[i][0].clear(),mp[i][1].clear(),mp[i][2].clear(),mp[i][3].clear();
tiers[0].pb(0);
REP(i,1,N){
tiers[hoursRequired(0,i)].pb(i);
}
REP(i,0,N+10)sort(all(tiers[i]));
REP(i,1,N+10){
if(!tiers[i].size())break;
int cur=0;
for(auto j:tiers[i]){
while(cur<tiers[i-1].size() && hoursRequired(tiers[i-1][cur],j)!=1)cur++;
assert(cur<tiers[i-1].size());
par[j]=tiers[i-1][cur];
}
}
REP(i,0,N+10)tiers[i].clear();
REP(i,1,N){
tiers[par[i]].pb(i);
}
REP(i,0,N){
REP(j,0,tiers[i].size()){
lkx[tiers[i][j]]=j;
// cerr<<tiers[i][j]<<" -> "<<j<<endl;
}
}
REP(i,0,N){
int cur=i;
int dst=0;
while(cur){
auto pxt=par[cur];
mp[pxt][lkx[cur]].insert({++dst,i});
cur=pxt;
}
mp[i][3].insert({0,i});
}
vector<int> ans;
int fnd=furthest(0).se;
ans.pb(fnd);
REP(_,1,N){
auto nxt=furthest(fnd);
int cur=fnd;
int dst=0;
while(cur){
auto pxt=par[cur];
mp[pxt][lkx[cur]].erase({++dst,fnd});
cur=pxt;
}
mp[fnd][3].erase({0,fnd});
ans.pb(fnd=nxt.se);
// cerr<<"! "<<nxt.se<<endl;
}
return ans;
}
