#include<bits/stdc++.h>
using namespace std ;
#define F first
#define S second
const int N = 1e5+5 ;
const int Q = 4e5+5 ;
int n , sub[N] , deep[N] ;
vector<int> ans , vd[N] , nei[N] ;
set<pair<int,int>> st[3] ;
int hoursRequired(int x , int y) ;
int attractionsBehind(int x , int y) ;
void dfs(int node , int t){
st[t].insert({-deep[node],node}) ;
for(int i:nei[node]){
deep[i]=deep[node]+1 ;
dfs(i,t) ;
}
}
vector<int> createFunTour(int n1 , int q){
n = n1 ;
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) , vd[deep[i]].push_back(i) ;
for(int i=1 ; i<=n ; i++){
for(int j:vd[i]){
int cnt = 0 ;
for(int l:vd[i-1]){
if(cnt==2 || hoursRequired(l,j)==1){
nei[l].push_back(j) ;
break ;
}
cnt++ ;
}
}
}
deep[pos]=0 ;
for(int i=0 ; i<nei[pos].size() ; i++) deep[nei[pos][i]]=1 , dfs(nei[pos][i],i) ;
// others code start
std::vector<int> siz(N);
siz[0] = N;
for (int i = 1; i < N; i++)
siz[i] = attractionsBehind(0, i);
int root = -1;
for (int i = 0; i < N; i++)
if (siz[i] >= (N + 1) / 2)
if (root == -1 || siz[root] > siz[i])
root = i;
std::vector<int> dist(N);
for (int i = 0; i < N; i++)
dist[i] = hoursRequired(root, i);
std::vector<int> sons;
std::vector<std::vector<int>> subtr;
for (int i = 0; i < N; i++)
if (dist[i] == 1)
sons.push_back(i);
subtr.resize(sons.size());
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 = [&dist](const int &x, const int &y) -> bool {
return dist[x] < dist[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));
}
for (auto &tr : subtr)
std::sort(tr.begin(), tr.end(), cmp);
// others code end
int s = 0 ;
for(int i=0 ; i<3 ; i++){
if(!st[i].empty()) s++ ;
}
assert(s==subtr.size()) ; //
for(int i=0 ; i<s ; i++){
assert(st[i].size()==subtr[i].size()) ; //
int pos = 0 ;
for(auto it:st[i]){
assert(it.S==subtr[i][pos]) ; //
pos++ ;
}
}
return {} ; //
/*
int t = -1 , sum = n-1 ;
while(sum){
int a = st[0].size() , b = st[1].size() , c = st[2].size() ;
if(abs(max({a,b,c})-(a+b+c-max({a,b,c})))<=1){
if(b>=a && b>=c){
swap(st[0],st[1]) ; swap(a,b) ;
if(t!=2) t=!t ;
}
if(c>=a && c>=b){
swap(st[0],st[2]) ; swap(a,c) ;
if(t!=1) t=2-t ;
}
if(t>0 && b+c>a){
if(st[3-t].empty()) return {} ; // assert
ans.push_back(st[3-t].begin()->S) ;
st[3-t].erase(st[3-t].begin()) ;
sum-- ;
}
for(auto it:st[2]) st[1].insert(it) ;
st[2].clear() ;
t=1 ;
break ;
}
int cur = -1 ;
for(int i=0 ; i<3 ; i++){
if(i==t || st[i].empty()) continue ;
if(cur==-1 || st[i].begin()->F<st[cur].begin()->F) cur = i ;
}
if(cur==-1) return {} ; // assert
t = cur ;
ans.push_back(st[cur].begin()->S) ;
st[cur].erase(st[cur].begin()) ;
sum-- ;
}
while(sum){
ans.push_back(st[!t].begin()->S) ;
st[!t].erase(st[!t].begin()) ;
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 ;
}
*/
