#include<bits/stdc++.h>
using namespace std ;
#define F first
#define S second
const int N = 1e5+5 ;
const int Q = 4e5+5 ;
int sub[N] , deep[N] ;
vector<int> ans , son ;
vector<vector<int>> subtr ;
int hoursRequired(int x , int y) ;
int attractionsBehind(int x , int y) ;
vector<int> createFunTour(int n , int q){
int pos = -1 ;
for(int i=0 ; i<n ; i++){
sub[i]=attractionsBehind(0,i) ;
if(sub[i]>=(n+1)/2 && (pos==-1 || sub[i]<sub[pos])) pos = i ;
}
for(int i=0 ; i<n ; i++){
deep[i]=hoursRequired(pos,i) ;
if(deep[i]==1) son.push_back(i) ;
}
subtr.resize(son.size()) ;
for(int i=0 ; i<n ; i++){
if(i==pos) continue ;
for(int j=0 ; j<3 ; j++){
if(j==2) subtr[j].push_back(i) ;
else if(deep[i]-deep[son[j]]==hoursRequired(i,son[j])) subtr[j].push_back(i) ;
else continue ;
break ;
}
}
// others code start
if(n==2) return {0,1} ;
for (int i = 0; i < N; i++) {
if (i == root)
continue;
bool found = false;
for (int j = 0; !found && j < 2; j++)
if (dist[i] - dist[sons[j]] == hoursRequired(i, sons[j]))
found = true, subtr[j].push_back(i);
if (!found)
subtr[2].push_back(i);
}
auto cmp = [&](const int &x, const int &y) -> bool {
return deep[x] < deep[y];
};
int sum = 0;
std::pair<int, int> max(0, -1);
for (int i = 0; i < 3; i++) {
sum += subtr[i].size();
max = std::max(max, std::make_pair((int)subtr[i].size(), i));
}
if (std::abs((sum - max.first) - max.first) <= 1) {
std::vector<int> idx;
for (int i = 0; i < 3; i++)
if (i != max.second)
idx.push_back(i);
subtr[idx[0]].insert(subtr[idx[0]].end(), subtr[idx[1]].begin(), subtr[idx[1]].end());
subtr.erase(subtr.begin() + idx[1]);
sons.erase(sons.begin() + idx[1]);
}
for (auto &tr : subtr)
std::sort(tr.begin(), tr.end(), cmp);
int last = -1, lastdis = 1e9;
if ((int)son.size() == 3) {
for (int i = 0; i < 3; i++)
if (last == -1 || deep[subtr[last].back()] < deep[subtr[i].back()])
last = i;
ans.push_back(subtr[last].back());
subtr[last].pop_back();
while (true) {
int nxt = -1;
for (int i = 0; i < 3; i++)
if (i != last && (nxt == -1 || deep[subtr[nxt].back()] < deep[subtr[i].back()]))
nxt = i;
ans.push_back(subtr[nxt].back());
subtr[nxt].pop_back();
int sum = 0;
std::pair<int, int> max(0, -1);
for (int i = 0; i < 3; i++) {
sum += subtr[i].size();
max = std::max(max, std::make_pair((int)subtr[i].size(), i));
}
if (std::abs((sum - max.first) - max.first) <= 1) {
std::vector<int> idx;
for (int i = 0; i < 3; i++)
if (i != max.second)
idx.push_back(i);
if (nxt == idx[0] && deep[ans.back()] < deep[subtr[idx[1]].back()])
nxt = idx[1], ans.push_back(subtr[nxt].back()), subtr[nxt].pop_back();
else if (nxt == idx[1] && deep[ans.back()] < deep[subtr[idx[0]].back()])
nxt = idx[0], ans.push_back(subtr[nxt].back()), subtr[nxt].pop_back();
if (nxt == idx[1])
nxt = idx[0];
if (nxt >= idx[1])
--nxt;
subtr[idx[0]].insert(subtr[idx[0]].end(), subtr[idx[1]].begin(), subtr[idx[1]].end());
std::sort(subtr[idx[0]].begin(), subtr[idx[0]].end(), cmp);
subtr.erase(subtr.begin() + idx[1]);
last = nxt;
break;
}
last = nxt;
}
} else {
last = (deep[subtr[0].back()] > deep[subtr[1].back()]) ? 0 : 1;
ans.push_back(subtr[last].back());
subtr[last].pop_back();
}
while (true) {
int nxt = last ^ 1;
ans.push_back(subtr[nxt].back());
subtr[nxt].pop_back();
if (subtr[last].empty() && (int)subtr[nxt].size() == 1) {
ans.push_back(subtr[nxt].back());
ans.push_back(pos);
return ans;
}
if (ans.size() == n - 1) {
ans.push_back(pos);
return ans;
}
last ^= 1;
}
/*
int t = -1 , sum = n-1 ;
while(sum){
int a = vp[0].size() , b = vp[1].size() , c = vp[2].size() ;
if(abs(max({a,b,c})-(a+b+c-max({a,b,c})))<=1){
if(b>=a && b>=c){
swap(vp[0],vp[1]) ; swap(a,b) ;
if(t!=2 && t!=-1) t=!t ;
}
if(c>=a && c>=b){
swap(vp[0],vp[2]) ; swap(a,c) ;
if(t!=1 && t!=-1) t=2-t ;
}
if(t) t=1 ;
//
if(t>0){
t = 3-t ;
// if(t==1 && deep[ans.back()]<-st[2].begin()->F) t=2 , ans.push_back(st[t].begin()->S) , st[t].erase(st[t].begin()) ;
// else if(t==2 && deep[ans.back()]<-st[1].begin()->F) t=1 , ans.push_back(st[t].begin()->S) , st[t].erase(st[t].begin()) ;
// else sum++ ;
// t = 1 ; sum-- ;
}
else if(t==-1) t=1 ;
//
for(auto it:vp[2]) vp[1].push_back(it) ;
sort(vp[1].begin(),vp[1].end()) ;
vp[2].clear() ;
break ;
}
int cur = -1 ;
for(int i=0 ; i<3 ; i++){
if(i!=t && (cur==-1 || vp[i].back().F<vp[cur].back().F)) cur = i ;
}
if(cur==-1) return {} ; //
t = cur ;
ans.push_back(vp[cur].back().S) ;
vp[cur].pop_back() ;
sum-- ;
}
while(sum){
if(vp[!t].empty()) t=!t ;
ans.push_back(vp[!t].back().S) ;
vp[!t].pop_back() ;
t=!t ; sum-- ;
}
ans.push_back(pos) ;
return ans ;
*/
}
/*
int hoursRequired(int x , int y){
cout << "h " << x << ' ' << y << '\n' ;
int k ; cin >> k ; return k ;
}
int attractionsBehind(int x , int y){
cout << "a " << x << ' ' << y << '\n' ;
int k ; cin >> k ; return k ;
}
int main(){
vector<int> v = createFunTour(7,Q-5) ; for(int i:v) cout << i << ' ' ; cout << '\n' ;
return 0 ;
}
*/
