#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define siz(A) ((int)A.size())

//bool are_connected(std::vector<int> A, std::vector<int> B);

#include "longesttrip.h"

random_device R;
mt19937 G(R());
int tms=0;
bool ck(int x,int y){return ++tms,are_connected({x},{y});}
vector<int>get(const vector<int>&A,int l,int r)
{
	vector<int>B;
	for(int i=l;i<=r;i++)B.push_back(A[i]);
	return B;
}
bool ck(int x,const vector<int>&B){return ++tms,are_connected({x},B);}
bool ck(const vector<int>&A,const vector<int>&B){return ++tms,are_connected(A,B);}
int rd(int l,int r){return uniform_int_distribution<int>(l,r)(G);}
std::vector<int> longest_trip(int N, int D)
{
	tms=0;
	assert(D>=1);
	vector<int>rem;
	vector<int>up,dw;
	for(int i=0;i<N;i++)rem.push_back(i);
	shuffle(rem.begin(),rem.end(),G);
	up.push_back(rem[0]);
	dw.push_back(rem[1]);
	rem.erase(rem.begin());
	rem.erase(rem.begin());
	while(siz(rem))
	{
		shuffle(rem.begin(),rem.end(),G);
		int A=rem[0];
		rem.erase(rem.begin());
		int T=rd(0,2);
		if(T==0)
		{
			if(ck(up.back(),A))up.push_back(A);
			else 
			{
				if(ck(dw.back(),A))dw.push_back(A);
				else 
				{
					reverse(dw.begin(),dw.end());
					up.insert(up.end(),dw.begin(),dw.end());
					dw.clear();
					dw.push_back(A);
				}
			}
		}
		else if(T==1)
		{
			if(ck(dw.back(),A))dw.push_back(A);
			else 
			{
				if(ck(up.back(),A))up.push_back(A);
				else 
				{
					reverse(dw.begin(),dw.end());
					up.insert(up.end(),dw.begin(),dw.end());
					dw.clear();
					dw.push_back(A);
				}
			}
		}
		else 
		{
			if(ck(up.back(),dw.back()))
			{
				reverse(dw.begin(),dw.end());
				up.insert(up.end(),dw.begin(),dw.end());
				dw.clear();
				dw.push_back(A);
			}
			else 
			{
				if(ck(up.back(),A))up.push_back(A);
				else dw.push_back(A);
			}
		}
		if(rd(0,1))reverse(up.begin(),up.end());
		if(rd(0,1))reverse(dw.begin(),dw.end());
	}
	assert(tms<=400);
	if(siz(dw)>siz(up))swap(up,dw);
//	for(auto it:up)cout<<it<<" ";
//	puts("");
//	for(auto it:dw)cout<<it<<" ";
//	puts("");
	if(!siz(dw))return up;
	if(ck(up.back(),dw.front()))
	{
		up.insert(up.end(),dw.begin(),dw.end());
		return up;
	}
	if(ck(up.front(),dw.front()))
	{
		reverse(up.begin(),up.end());
		up.insert(up.end(),dw.begin(),dw.end());
		return up;
	}
	if(ck(up.back(),dw.back()))
	{
		reverse(dw.begin(),dw.end());
		up.insert(up.end(),dw.begin(),dw.end());
		return up;
	}
	if(ck(up.front(),dw.back()))
	{
		reverse(dw.begin(),dw.end());
		reverse(up.begin(),up.end());
		up.insert(up.end(),dw.begin(),dw.end());
		return up;
	}
	//两边开头结尾都有边
	/* 
	int L=0,R=siz(dw)-1,op=0;
	while(L<=R)
	{
		int cl=L,cr=R;
		if(!ck(up.back(),get(dw,cl,cr)))
		{
				//两端都不行了，且两端有连边。 
			if(op)break;
			op=1;
			reverse(up.begin(),up.end());
			continue;
		}
		while(cl<cr)
		{
			int mid=cl+cr>>1;
			if(ck(up.back(),get(dw,cl,mid)))cr=mid;
			else cl=mid+1;
		}
		if(cl<=(L+R>>1))
			up.insert(up.end(),dw.begin()+cl,dw.begin()+R+1),R=cl-1;
		else 
		{
			for(int i=cl;i>=L;i--)up.push_back(dw[i]);
			L=cl+1;
		}
	}
	if(L<=R)
	{*/
//		dw=get(dw,L,R);
		if(!ck(up,dw))
		{
			if(siz(dw)>siz(up))swap(dw,up);
			return up;
		}
		int l=0,r=siz(up)-1,L=0,R=siz(dw)-1;
		while(l<r)
		{
			int mid=l+r>>1;
			if(ck(get(up,l,mid),get(dw,L,R)))r=mid;
			else l=mid+1;
		}
		while(L<R)
		{
			int mid=L+R>>1;
			if(ck(get(up,l,r),get(dw,L,mid)))R=mid;
			else L=mid+1;
		}
		rotate(up.begin(),up.begin()+l,up.end());
		rotate(dw.begin(),dw.begin()+L,dw.end());
		reverse(up.begin(),up.end());
		up.insert(up.end(),dw.begin(),dw.end());
		return up;
//	}
//	else return up;
	
	
	
    return {};
}