#include "longesttrip.h"

#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
std::mt19937 rnd(114514);
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> 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;
	if(d==2){
		for(int i=1;i<n;++i)for(int j=i+1;j<=n;++j)g[i][j]=g[j][i]=are_connected({i-1},{j-1});
		vector<int> nodes(0);
		for(int i=0;i<n;++i){
			nodes.emplace_back(i+1);
		}
		build2(nodes);
	}
	else{
		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){
			if(rnd()&1)c1.swap(c2);
			if(G(c1.back(),i)){
				c1.emplace_back(i);
			}
			else if(G(c2.back(),i)){
				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;
}