#include <cstdio>
#include <vector>
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>adj[1005];
int vis[10005];
int can[10005];
void dfs(int u){
vis[u]=1;
for(auto x:adj[u])if(vis[x]==0&&can[x])dfs(x);
}
int p[1005];
int cnt[1005];
int fp(int a){
if(p[a]==a)return a;
return p[a]=fp(p[a]);
}
void un(int a,int b){
p[fp(a)]=fp(b);
}
int con(vector<int>v){
vector<int>temp(n);
int tot=0;
for(int i=1;i<=n;i++)vis[i]=0,can[i]=0;
for(auto x:v)can[x]=1;
for(auto x:v){
temp[x-1]=1;
if(vis[x])continue;
dfs(x);
tot++;
}
/*cerr<<"QR:\n";
for(auto x:temp)cerr<<x<<" ";
cerr<<"\n";*/
int res=Query(temp);
//cerr<<"res:"<<tot<<' '<<res<<"\n";
return tot==res;
}
vector<int>rans;
void dfs(int u,int p){
rans.push_back(u);
for(auto x:adj[u])if(x!=p)dfs(x,u);
}
void Solve(int N)
{
for(int i=0;i<=N;i++)adj[i].clear();
n=N;
for(int i=1;i<=N;i++)p[i]=i;
for(int i=1;i<N;i++){
//cerr<<"i:"<<i<<"\n";
int st=1,en=N,ans=0;
while(st<=en){
int m=(st+en)/2;
vector<int>temp;
for(int i=1;i<=m;i++)temp.push_back(i);
if(con(temp)){
st=m+1;
}else{
en=m-1;
ans=m;
}
}
assert(ans!=0);
int rans=0;
assert(ans!=1);
st=1,en=ans-1;
//cerr<<"ANS:"<<ans<<"\n";
while(st<=en){
int m=(st+en)/2;
vector<int>temp;
temp.push_back(ans);
for(int i=1;i<=m;i++)temp.push_back(i);
/*cerr<<"m:"<<m<<"\n";
for(auto x:temp)cerr<<x<<" ";
cerr<<"\n";*/
int tt=con(temp);
//cerr<<"con? "<<tt<<"\n";
if(tt){
assert(m!=(ans-1));
st=m+1;
}else{
rans=m;
en=m-1;
}
}
assert(rans!=0);
assert(fp(rans)!=fp(ans));
un(rans,ans);
adj[rans].push_back(ans);
adj[ans].push_back(rans);
//cerr<<"edge:"<<ans<<" "<<rans<<"\n";
}
int rt=1;
for(int i=1;i<=N;i++)if(adj[i].size()==1)rt=i;
//assert(rt!=0);
dfs(rt,0);
assert(adj[0].size()==0);
//for(auto x:rans)cerr<<x<<" ";
//cerr<<"\n";
Answer(rans);
}
