#include "longesttrip.h"

#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
std::mt19937 rnd(123456789);
int g[305][305];
vector<int> ans;
void build2(vector<int> &node){
	int x=0,y=0;
	for(auto i:node)for(auto j:node)if(i!=j && !g[i][j]){
		x=i;y=j;
		break;
	}
	if(!x){
		for(auto i:node)ans.emplace_back(i);
		return;
	}
	for(int i=node.size()-1;~i;--i)if(node[i]==x || node[i]==y){
		swap(node[i],node.back());
		node.pop_back();
	}
	if(node.size()<=2){
		if(node.size()==1){
			ans.emplace_back(x);ans.emplace_back(node[0]);ans.emplace_back(y);
		}
		else{
			ans.emplace_back(x);ans.emplace_back(node[0]);ans.emplace_back(y);ans.emplace_back(node[1]);
		}
	}
	else{
		build2(node);
		ans.emplace(ans.begin(),x);
		ans.emplace_back(y);
	}
}
vector<int> c1,c2;
bool G(int x,int y){
	if(g[x][y]!=-1)return g[x][y];
	else return g[x][y]=g[y][x]=are_connected({x-1},{y-1});
}
void shift(vector<int> &a,int x){
	vector<int> b(0);
	// let x be the 1st element of a
	int oc=0;
	for(auto i:a){
		if(i==x)oc=1;
		if(oc)b.emplace_back(i);
	}
	for(auto i:a){
		if(i==x)break;
		b.emplace_back(i);
	}
	a.swap(b);
}
bool find_any(vector<int> a,vector<int> b,int &ax,int &ay){
	for(auto &i:a)--i;
	for(auto &i:b)--i;
	if(!are_connected(a,b)){ax=ay=0;return 0;}
	int l=0,r=b.size()-1;
	while(l<r){
		int mid=(l+r)>>1;
		if(are_connected(a,vector<int>(b.begin()+l,b.begin()+mid+1)))r=mid;
		else l=mid+1;
	}
	int x=b[l];
	l=0,r=a.size()-1;
	while(l<r){
		int mid=(l+r)>>1;
		if(are_connected(vector<int>(a.begin()+l,a.begin()+mid+1),{x}))r=mid;
		else l=mid+1;
	}
	ax=a[l]+1;ay=x+1;
	return 1;
}
std::vector<int> vec;
std::vector<int> v3({0,1,2});
std::vector<int> longest_trip(int n, int d)
{
	ans.clear();
	if(d==3){
		for(int i=0;i<n;++i)ans.emplace_back(i);
		return ans;
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)g[i][j]=-1;
	c1.clear();c2.clear();
	vec.clear();
	for(int i=2;i<=n;++i)vec.emplace_back(i);
	shuffle(vec.begin(),vec.end(),rnd);
	c1.emplace_back(vec.back());
	vec.pop_back();
	c2.emplace_back(vec.back());
	vec.pop_back();
	for(auto i:vec){
		shuffle(v3.begin(),v3.end(),rnd);
		for(int j=0;j<3;++j){
			bool chk=0;
			if(j!=2){
				if(v3[j]==0)chk=G(c1.back(),i);
				else if(v3[j]==1)chk=G(c2.back(),i);
				else chk=G(c1.back(),c2.back());
			}
			else chk=1;
			if(chk){
				if(v3[j]==0)c1.emplace_back(i);
				else if(v3[j]==1)c2.emplace_back(i);
				else{
					while(!c2.empty()){c1.emplace_back(c2.back());c2.pop_back();}
					c2.emplace_back(i);
				}
			}
		}
	}
	int v11=G(1,c1[0]),v12=G(1,c1.back());
	int v21=G(1,c2[0]),v22=G(1,c2.back());
	if((v11||v12) && (v21||v22)){
		if(v11){
			reverse(c1.begin(),c1.end());
		}	
		if(v22){
			reverse(c2.begin(),c2.end());
		}	
		for(auto i:c1)ans.emplace_back(i);
		ans.emplace_back(1);
		for(auto i:c2)ans.emplace_back(i);
	}
	else{
		if(!(v11+v12+v21+v22)){
			for(auto i:c2)c1.emplace_back(i);
			int ax=0,ay=0;
			find_any({c1},{1},ax,ay);
			if(!ax)ans=c1;
			else{
				shift(c1,ax);
				c1.emplace(c1.begin(),1);
				ans=c1;
			}
		}
		else{
			if(v11+v12){
				swap(c1,c2);
				swap(v11,v21);swap(v12,v22);
			}
			if(v22){
				reverse(c2.begin(),c2.end());
				swap(v21,v22);
				// 能联通的放到begin
			}
			if(!v22){
				ans.emplace_back(1);
				for(auto i:c2)ans.emplace_back(i);
				for(auto i:c1)ans.emplace_back(i);
				goto END;
			}
			c2.emplace_back(1);
			int ax=0,ay=0;
			find_any(c2,c1,ax,ay);
			if(!ax){
				if(c1.size()>c2.size()){
					ans=c1;
				}
				else ans=c2;
			}
			else{
				shift(c1,ay);
				shift(c2,ax);
				reverse(c1.begin(),c1.end());
				for(auto i:c1)ans.emplace_back(i);
				for(auto i:c2)ans.emplace_back(i);
			}	
		}
	}
END:;
	for(auto &i:ans){i-=1;}
	return ans;
}