#include "longesttrip.h"

#include<vector>
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);
	}
}
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 || d==1){
		vector<int> nodes(0);
		for(int i=0;i<n;++i){
			nodes.emplace_back(i+1);
		}
		build2(nodes);
	}
	for(auto &i:ans){i-=1;}
	return ans;
}