#include "longesttrip.h"
#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e3+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n;
int B[N],C[N],Bh,Ch,siz,P1,P2;
int qry(int x,int y){
	return are_connected({x},{y});
}
int qrys(int x,int op){
	vector<int> S;
	for(int i=1;i<=(op?Bh:Ch);i++) S.emplace_back(i[op?B:C]);
	return are_connected({x},S);
}
int qs(int x,vector<int> S){
	return are_connected({x},S);
}
int calc(vector<int> B,int x){
	if(B.size()==1) return B[0];
	int Le=B.size()/2;
	vector<int> S1(B.begin(),B.begin()+Le),S2(B.begin()+Le,B.end());
	if(qs(x,S1)) return calc(S1,x);
	else return calc(S2,x);
}
vector<int> longest_trip(int nn,int dd){
	int i,j;n=nn;
	Bh=Ch=0;siz=1;P1=P2=-1;
	B[++Bh]=0;
	for(i=1;i<n;i++){
		if(rnd()&1) swap(P1,P2);
		if(rnd()&1) reverse(B+1,B+Bh+1);
		if(rnd()&1) reverse(C+1,C+Ch+1);
		if(siz==1){
			if(qry(B[Bh],i)) B[++Bh]=i;
			else if(qry(B[1],i)) {
				if(P1==-1) P1=i,P2=B[Bh];
				B[++Bh]=i,rotate(B+1,B+Bh,B+Bh+1);
			}
			else {
				if(~P1){
					if(qry(P1,i)) {
						rotate(B+1,find(B+1,B+Bh+1,P1),B+Bh+1);
						B[++Bh]=i;
						rotate(B+1,B+Bh,B+Bh+1);
					}else{
						rotate(B+1,find(B+1,B+Bh+1,P2),B+Bh+1);
						B[++Bh]=i;
						rotate(B+1,B+Bh,B+Bh+1);
					}
				}else{
					int flag=0,Lp=B[1];
					if(!qrys(i,1)){
						C[++Ch]=i;siz=2;
					}else{
						vector<int> BB;
						for(int j=2;j<Bh;j++) BB.emplace_back(B[j]);
						int p=calc(BB,i);
						rotate(B+1,find(B+1,B+Bh+1,p),B+Bh+1);
						B[++Bh]=i;
						rotate(B+1,B+Bh,B+Bh+1);
					}
					/*for(int j=2;j<Bh;j++) if(qry(B[j],i)) {
						flag=1;
						rotate(B+1,B+j,B+Bh+1);
						B[++Bh]=i;
						rotate(B+1,B+Bh,B+Bh+1);
						break;
					}
					if(!flag) C[++Ch]=i,siz=2;
					else if(P1==-1) P1=i,P2=Lp;*/
				}
			}
		}else{
			if(!qrys(i,1)){
				C[++Ch]=i;
			}else{
				if(!qrys(i,0)) B[++Bh]=i;
				else {
					vector<int> S(B+1,B+Bh+1);
					int p=calc(S,i);
					rotate(B+1,find(B+1,B+Bh+1,p),B+Bh+1);
					B[++Bh]=i;
					rotate(B+1,B+Bh,B+Bh+1);
					for(int j=1;j<=Ch;j++) if(qry(C[j],i)){
						rotate(C+1,C+j,C+Ch+1);
						C[++Ch]=i;
						rotate(C+1,C+Ch,C+Ch+1);
						break;
					}
					if(P1==-1) P1=B[Bh],P2=C[Ch];
					reverse(C+1,C+Ch+1);
					copy(C+1,C+Ch,B+Bh+1);
					rotate(B+1,B+Bh+1,B+Bh+Ch);
					Bh+=Ch-1;Ch=0;siz=1;
				}
			}
		}
	}
	vector<int> ans;
	if(Bh>Ch){
		for(int i=1;i<=Bh;i++) ans.emplace_back(B[i]);
	}else{
		for(int i=1;i<=Ch;i++) ans.emplace_back(C[i]);
	}
	return ans;
}