#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
bool youbian(int x,int y)
{
	vector<int>v1,v2;
	v1.push_back(x);
	v2.push_back(y);
	return are_connected(v1,v2);
}
int p[1005];
mt19937 ran(121296);
int findlink(int x,vector<int>v)
{
	/*if(v.size()>=64)
	{
		int gre=ran()%v.size();
		//printf("%d %d\n",x,v[gre]);
		if(youbian(x,v[gre]))return v[gre];
	}*/
	vector<int>sth;
	sth.push_back(x);
	int l=0,r=v.size()-1,mid;
	while(l<r)
	{
		mid=((l+r)>>1);
		vector<int>xw;
		for(int i=l;i<=mid;i++)xw.push_back(v[i]);
		if(are_connected(sth,xw))r=mid;
		else l=mid+1;
	}
	return v[l];
}
std::vector<int> longest_trip(int N, int D)
{
	if(D==3)
	{
		vector<int>v;
		for(int i=0;i<N;i++)v.push_back(i);
		return v;
	}
	if(D==2)
	{
		vector<int>v;
		int sth=1;
		if(!youbian(0,2))sth=2;
		if(!youbian(1,2))sth=3;
		if(sth==1)
		{
			v.push_back(0);
			v.push_back(2);
			v.push_back(1);
		}
		else if(sth==2)
		{
			v.push_back(0);
			v.push_back(1);
			v.push_back(2);
		}
		else
		{
			v.push_back(1);
			v.push_back(0);
			v.push_back(2);
		}
		for(int i=3;i<N;i++)
		{
			if(!youbian(v[v.size()-1],i))reverse(v.begin(),v.end());
			v.push_back(i);
		}
		return v;
	}
	for(int i=0;i<N;i++)p[i]=i;
	for(int i=0;i<N;i++)swap(p[i],p[ran()%(i+1)]);
	vector<int>lt1,lt2;
	lt1.push_back(p[0]);
	if(youbian(p[0],p[1]))lt1.push_back(p[1]);
	else lt2.push_back(p[1]);
	for(int i=2;i<N;i++)
	{
		//printf("orz%d\n",i);
		if(!lt2.empty())
		{
			//printf("!!!\n");
			vector<int>sth;
			sth.push_back(p[i]);
			if(lt1.size()>lt2.size())swap(lt1,lt2);
			if(!are_connected(lt1,sth))lt2.push_back(i);
			else if(!are_connected(lt2,sth))lt1.push_back(i);
			else
			{
				int x=findlink(p[i],lt1),y=findlink(p[i],lt2);
				vector<int>now;
				for(int i=0;i<lt1.size();i++)if(lt1[i]!=x)now.push_back(lt1[i]);
				now.push_back(x);
				now.push_back(p[i]);
				now.push_back(y);
				for(int i=0;i<lt2.size();i++)if(lt2[i]!=y)now.push_back(lt2[i]);
				lt1=now;
				lt2.clear();
			}
		}
		else
		{
			vector<int>sth;
			sth.push_back(p[i]);
			if(ran()%2)reverse(lt1.begin(),lt1.end());
			//printf("hello%d\n",(int)lt1.size());
			if(youbian(lt1[lt1.size()-1],p[i]))lt1.push_back(p[i]);
			else if(youbian(lt1[0],p[i]))
			{
				reverse(lt1.begin(),lt1.end());
				lt1.push_back(p[i]);
			}
			else if(lt1.size()<=2)
			{
				lt2.push_back(p[i]);
				continue;
			}
			else if(!are_connected(sth,lt1))
			{
				lt2.push_back(p[i]);
				continue;
			}
			else
			{
				//printf("orz?\n");
				vector<int>xw;
				for(int i=1;i<lt1.size()-1;i++)xw.push_back(lt1[i]);
				assert(!xw.empty());
				int x=findlink(p[i],xw);
				int pos=0;
				for(int i=0;i<lt1.size();i++)
				{
					if(lt1[i]==x)
					{
						pos=i;
						break;
					}
				}
				vector<int>now;
				now.push_back(p[i]);
				for(int i=pos;i<lt1.size();i++)now.push_back(lt1[i]);
				for(int i=0;i<pos;i++)now.push_back(lt1[i]);
				lt1=now;
			}
		}
	}
	if(lt1.size()<lt2.size())swap(lt1,lt2);
    return lt1;
}