//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include "longesttrip.h"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll int
#define N 260
using namespace std;
ll n,fa[N];
bool hved[N][N];
ll getf(ll x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
vector<ll> solve(vector<ll> v)
{
	if(v.size()<=1)
	{
		return v;
	}
	ll i,j;
	vector<ll> sons;
	for(i=1;i<v.size();i++)
	{
		sons.push_back(v[i]);
	}
	vector<ll> v1,v2;
	for(i=0;i<sons.size();i++)
	{
		fa[sons[i]]=sons[i];
	}
	for(i=0;i<sons.size();i++)
	{
		for(j=i+1;j<sons.size();j++)
		{
			if(hved[sons[i]][sons[j]])
			{
				fa[getf(sons[i])]=getf(sons[j]);
			}
		}
	}
	for(i=0;i<sons.size();i++)
	{
		if(getf(sons[i])==getf(sons[0]))
		{
			v1.push_back(sons[i]);
		}
		else
		{
			v2.push_back(sons[i]);
		}
	}
	v1=solve(v1);
	v2=solve(v2);
	if(!v1.empty())
	{
		if(!hved[v1[0]][v[0]])
		{
			for(i=0;i<v1.size();i++)
			{
				if(hved[v1[i]][v[0]]&&(i==v1.size()-1||(!hved[v1[i+1]][v[0]])))
				{
					reverse(v1.begin(),v1.begin()+i+1);
					break;
				}
			}
		}
		reverse(v1.begin(),v1.end());
	}
	if(!v2.empty())
	{
		if(!hved[v2[0]][v[0]])
		{
			for(i=0;i<v2.size();i++)
			{
				if(hved[v2[i]][v[0]]&&(i==v2.size()-1||(!hved[v2[i+1]][v[0]])))
				{
					reverse(v2.begin(),v2.begin()+i+1);
					break;
				}
			}
		}
	}
	v1.push_back(v[0]);
	for(i=0;i<v2.size();i++)
	{
		v1.push_back(v2[i]);
	}
	return v1;
}
vector<int> longest_trip(int _n,int _d)
{
	ll i,j;
	n=_n;
	for(i=0;i<n;i++)
	{
		fa[i]=i;
		for(j=i+1;j<n;j++)
		{
			hved[i][j]=hved[j][i]=are_connected(vector<int>{i},vector<int>{j});
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(hved[i][j])
			{
				fa[getf(i)]=getf(j);
			}
		}
	}
	vector<ll> v1,v2;
	for(i=0;i<n;i++)
	{
		if(getf(i)==getf(0))
		{
			v1.push_back(i);
		}
		else
		{
			v2.push_back(i);
		}
	}
	if(v1.size()>v2.size())
	{
		return solve(v1);
	}
	return solve(v2);
}