#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
using namespace std;
typedef long long ll;
const int mx=5e2+12;
vector<int> g[mx];
int was[mx][mx];
bool are_connected(std::vector<int> A, std::vector<int> B);
int ask(int a,int b){
if(!was[a][b]){
was[a][b]=was[b][a]=(int)are_connected({a},{b})+1;
}
return was[a][b]-1;
}
std::vector<int> longest_trip(int n, int d){
vector<int> ans;
if(d==3){
for(int i=0;i<n;i++){
ans.push_back(i);
}
return ans;
}
bool used[n+12]={};
if(d==2){
deque<int> ans;
ans.push_back(0);
for(int i=1;i<n;i++){
if(are_connected({0},{i})){
ans.push_back(i);
used[0]=1;
used[i]=1;
break;
}
}
for(int i=1;i<n;i++){
if(used[i]){
continue;
}
if(are_connected({ans.back()},{i})){
ans.push_back(i);
}
else{
ans.push_front(i);
}
}
vector<int> v;
for(int x:ans){
v.push_back(x);
}
return v;
}
for(int i=0;i<n;i++){
g[i].clear();
for(int j=0;j<n;j++){
was[i][j]=0;
}
}
srand(time(0));
vector<int> t;
for(int i=0;i<n;i++){
g[i].push_back(i);
t.push_back(i);
}
while(t.size()>2){
int a=t[0],b=t[1],c=t[2];
vector<pair<int,int>> d;
d.push_back({a,b});
d.push_back({a,c});
d.push_back({b,c});
random_shuffle(d.begin(),d.end());
int v,u;
if(ask(d[0].f,d[0].s)){
v=d[0].f,u=d[0].s;
}
else if(ask(d[1].f,d[1].s)){
v=d[1].f,u=d[1].s;
}
else{
v=d[2].f,u=d[2].s;
}
reverse(g[v].begin(),g[v].end());
for(int x:g[u]){
g[v].push_back(x);
}
g[u].clear();
int x=g[v][0];
if(x!=v){
for(int to:g[v]){
g[x].push_back(to);
}
g[v].clear();
}
t.clear();
for(int i=0;i<n;i++){
if((int)g[i].size()>0){
t.push_back(i);
}
}
}
int a=t[0],b=t[1];
if(are_connected(g[a],g[b])){
vector<int> ans;
vector<int> v=g[a],u=g[b];
if(ask(v[0],u.back())){
ans=u;
for(int x:v){
ans.push_back(x);
}
return ans;
}
if(ask(v[0],u[0])){
reverse(u.begin(),u.end());
ans=u;
for(int x:v){
ans.push_back(x);
}
return ans;
}
if(ask(v.back(),u[0])){
ans=v;
for(int x:u){
ans.push_back(x);
}
return ans;
}
if(ask(v.back(),u.back())){
ans=v;
reverse(u.begin(),u.end());
for(int x:u){
ans.push_back(x);
}
return ans;
}
int pos=-1,pos1=-1;
for(int l=1,r=v.size();l<=r;){
int mid=l+r>>1;
vector<int> t;
for(int i=0;i<mid;i++){
t.push_back(v[i]);
}
if(are_connected(t,u)){
pos=mid-1;
r=mid-1;
}
else{
l=mid+1;
}
}
for(int l=1,r=u.size();l<=r;){
int mid=l+r>>1;
vector<int> t;
for(int i=0;i<mid;i++){
t.push_back(u[i]);
}
if(are_connected({v[pos]},t)){
pos1=mid-1;
r=mid-1;
}
else{
l=mid+1;
}
}
vector<int> x,y;
for(int i=pos;i<v.size();i++){
x.push_back(v[i]);
}
for(int i=0;i<pos;i++){
x.push_back(v[i]);
}
for(int i=pos1;i<u.size();i++){
y.push_back(u[i]);
}
for(int i=0;i<pos1;i++){
y.push_back(u[i]);
}
reverse(x.begin(),x.end());
for(int t:x){
ans.push_back(t);
}
for(int t:y){
ans.push_back(t);
}
return ans;
}
else{
if((int)g[a].size()>(int)g[b].size()){
return g[a];
}
else{
return g[b];
}
}
}
