#include "longesttrip.h"

#include<vector>
#include<algorithm>
using namespace std;
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){
	return g[x][y];
}
void shift(vector<int> &a,int x){
	vector<int> b(0);
	a.swap(b);
	// 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);
	}
}
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=i+1;j<=n;++j)g[i][j]=g[j][i]=are_connected({i-1},{j-1});
	if(d==2){
		vector<int> nodes(0);
		for(int i=0;i<n;++i){
			nodes.emplace_back(i+1);
		}
		build2(nodes);
	}
	else{
		c1.clear();c2.clear();
		c1.emplace_back(2);c2.emplace_back(3);
		for(int i=4;i<=n;++i){
			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;
				for(auto i:c1)if(G(1,i)){
					ax=i;
					break;
				}
				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;
				}
				int ax=0,aid=0;
				for(int id=0;id<c1.size();++id){
					int i=c1[id];
					if(G(1,i)){
						ax=i;	
						aid=id;
						break;
					}
				}
				if(ax){
					for(int i=aid+1;i<c1.size();++i){
						ans.emplace_back(c1[i]);
					}
					for(int i=0;i<=aid;++i)ans.emplace_back(c1[i]);
					ans.emplace_back(1);
					for(auto i:c2)ans.emplace_back(i);
				}
				else{
					int ax=0,ay=0;
					for(auto i:c2){
						for(auto j:c1){
							if(G(i,j)){
								ax=i;ay=j;

								break;
							}
						}
						if(ax)break;
					}
					if(!ax){
						c2.emplace_back(1);
						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;
}