#include"longesttrip.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<random>
#define N 256
using namespace std;
mt19937 RAND(random_device{}());
int n,P[N+1],lg[N+1];
bool check(int x,int y)
{
	return are_connected({x},{y});
}
bool check2(vector<int>p,int d,int x)
{
	vector<int>q;
	for (int i=d;i<p.size();++i) q.push_back(p[i]);
	return are_connected(q,{x});
}
bool check3(vector<int>p,int d,int x)
{
	vector<int>q;
	for (int i=0;i<=d;++i) q.push_back(p[i]);
	return are_connected(q,{x});
}
vector<int>longest_trip(int SN, int D)
{
	vector<int>p;
	vector<int>p2;
	vector<int>q;
	int x;
	bool opt=0;
	n=SN;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
    if (D==3)
	{
		for (int i=0;i<n;++i) p.push_back(i);
		return p;
	}
	else if (D==2)
	{
		if (!check(0,1)) p.push_back(0),p.push_back(2),p.push_back(1);
		else if (!check(0,2)) p.push_back(0),p.push_back(1),p.push_back(2);
		else p.push_back(1),p.push_back(0),p.push_back(2);
		for (int i=3;i<n;++i)
		{
			if (!check(p.back(),i)) reverse(p.begin(),p.end());
			p.push_back(i);
		}
		return p;
	}
	else
	{
		for (int i=0;i<n;++i) P[i]=i;
		shuffle(P,P+n,RAND),p.push_back(P[0]);
		for (int i=1;i<n;++i)
		{
			if (p2.empty())
			{
				if (RAND()&1) reverse(p.begin(),p.end());
				if (check(p.back(),{P[i]})) p.push_back(P[i]),opt=0;
				else if (opt||check(p[0],{P[i]})) reverse(p.begin(),p.end()),p.push_back(P[i]),opt=1;
				else if (!are_connected(p,{P[i]})) p2.push_back(P[i]),opt=0;
				else
				{
					x=p.size()-1,q.clear();
					if (p.size()>=3)
					{
						if (check2(p,p.size()-2,P[i])) x--;
						else
						{
							for (int j=lg[p.size()];j>=0;--j)
								if (x-(1<<j)>=1&&!check2(p,x-(1<<j),P[i]))
									x-=(1<<j);
							x--;
						}
					}
					else
					{
						for (int j=lg[p.size()];j>=0;--j)
							if (x-(1<<j)>=1&&!check2(p,x-(1<<j),P[i]))
								x-=(1<<j);
						x--;
					}
					for (int j=(int)(p.size())-1;j>=x+1;--j) q.push_back(p[j]);
					for (int j=0;j<=x;++j) q.push_back(p[j]);
					q.push_back(P[i]),p=q,opt=0;
				}
			}
			else
			{
				if (RAND()&1) reverse(p.begin(),p.end());
				if (RAND()&1) reverse(p2.begin(),p2.end());
				if (min(p.size(),p2.size())>70)
				{
					if (p.size()>p2.size()) swap(p,p2);
				}
				else
				{
					if (p.size()<p2.size()) swap(p,p2);
				}
				if (!are_connected(p2,{P[i]})) p.push_back(P[i]),opt=0;
				else if (!are_connected(p,{P[i]})) p2.push_back(P[i]),opt=0;
				else
				{
					x=-1,q.clear();
					if (check(p[0],P[i])) x=0;
					else
					{
						for (int j=lg[p.size()];j>=0;--j)
							if (x+(1<<j)+1<p.size()&&!check3(p,x+(1<<j),P[i]))
								x+=(1<<j);
						x++;
					}
					for (int j=0;j<p.size();++j)
						if (j!=x)
							q.push_back(p[j]);
					q.push_back(p[x]),q.push_back(P[i]),x=-1;
					if (check(p2[0],P[i])) x=0;
					else
					{
						for (int j=lg[p2.size()];j>=0;--j)
							if (x+(1<<j)+1<p2.size()&&!check3(p2,x+(1<<j),P[i]))
								x+=(1<<j);
						x++;
					}
					q.push_back(p2[x]);
					for (int j=0;j<p2.size();++j)
						if (j!=x)
							q.push_back(p2[j]);
					p=q,p2.clear(),opt=1;
				}
			}
		}
		if (p.size()<p2.size()) swap(p,p2);
		return p;
	}
}