# include "longesttrip.h"
# include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
vi longest_trip(int n,int D)
{
	static int a[300];
	vi a1,a2;
	mt19937 rnd;
	iota(a,a+n,0);
	shuffle(a,a+n,rnd);
	a1={a[0]};
	for(int i=1;i<n;i++)
	{
		int u=a[i];
		if(a1.empty()) swap(a1,a2);
		if(a2.empty())
		{
			if(rnd()&1) reverse(a1.begin(),a1.end());
			if(i+1<n)
			{
				int v=a[++i];
				if(are_connected({u},{v}))
				{
					if(are_connected({a1.front()},{u})) a1.insert(a1.begin(),u),a1.insert(a1.begin(),v);
					else a2={u,v};
				}
				else
				{
					if(are_connected({a1.front()},{u})) a1.insert(a1.begin(),u),a2={v};
					else a1.insert(a1.begin(),v),a2={u};
				}
			}
			else if(are_connected({a1.front()},{u})) a1.insert(a1.begin(),u);
			else a2={u};
		}
		else
		{
			if(rnd()&1) swap(a1,a2);
			if(are_connected({a1.front()},{u}))
			{
				if(i+1<n)
				{
					int v=a[++i];
					if(are_connected({u},{v}))
					{
						if(are_connected({a2.front()},{v}))
						{
							reverse(a1.begin(),a1.end());
							a1.push_back(u);
							a1.push_back(v);
							a1.insert(a1.end(),a2.begin(),a2.end());
							a2.clear();
						}
						else a1.insert(a1.end(),u),a1.insert(a1.end(),v);
					}
					else if(are_connected({a2.front()},{u}))
					{
						reverse(a1.begin(),a1.end());
						a1.push_back(u);
						a1.insert(a1.end(),a2.begin(),a2.end());
						a2.clear();i--;
					}
					else a1.insert(a1.begin(),u),a2.insert(a2.begin(),v);
				}
				if(are_connected({a2.front()},{u}))
				{
					reverse(a1.begin(),a1.end());
					a1.push_back(u);
					a1.insert(a1.end(),a2.begin(),a2.end());
					a2.clear();
				}
				else a1.insert(a1.begin(),u);
			}
			else a2.insert(a2.begin(),u);
		}
	}
	if(a1.empty()) swap(a1,a2);
	if(a2.empty()) return a1;
	if(!are_connected(a1,a2)) return a1.size()>a2.size()?a1:a2;
	if(!are_connected(a1.size()>1?vi{a1.front(),a1.back()}:a1,a2.size()>1?vi{a2.front(),a2.back()}:a2))
	{
		int l1=0,r1=a1.size()-1,l2=0,r2=a2.size()-1,mid;
		while(l1<r1)
		{
			mid=(l1+r1)/2;
			if(are_connected(vi(a1.begin()+mid+1,a1.begin()+r1+1),a2)) l1=mid+1;
			else r1=mid;
		}
		while(l2<r2)
		{
			mid=(l2+r2)/2;
			if(are_connected({a1[l1]},vi(a2.begin()+mid+1,a2.begin()+r2+1))) l2=mid+1;
			else r2=mid;
		}
		if(l1+1<a1.size()) rotate(a1.begin(),a1.begin()+l1+1,a1.end());
		rotate(a2.begin(),a2.begin()+l2,a2.end());
		a1.insert(a1.end(),a2.begin(),a2.end());
		return a1;
	}
	else if(are_connected({a1.front()},{a2.back()}))
	{
		a2.insert(a2.end(),a1.begin(),a1.end());
		return a2;
	}
	else if(are_connected({a1.back()},{a2.front()}))
	{
		a1.insert(a1.end(),a2.begin(),a2.end());
		return a1;
	}
	else
	{
		reverse(a2.begin(),a2.end());
		a1.insert(a1.end(),a2.begin(),a2.end());
		return a1;
	}
}