#include "longesttrip.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using u64=unsigned long long;
using lf=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define ct const
#define il inline
#define pb push_back
#define fi first
#define se second
template<class T>
il void tomn(T&x,T ct&y){y<x?x=y,0:0;}
template<class T>
il void tomx(T&x,T ct&y){y>x?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const lf EPS=1e-10L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const ll INF=4e18L;

namespace SOL{
	ct int N=300;
	using Arr=vector<int>;
	int n,d;
	bool qry(Arr x,Arr y){return are_connected(x,y);}
	namespace D3{
		Arr main(){
			Arr ret{};
			F(i,0,n-1)ret.pb(i);
			return ret;
		}
	}
	namespace D2{
		bool vis[N];
		Arr main(){
			F(i,0,n)vis[i]=0;
			Arr ret{0};
			int p=0;vis[0]=1;
			F(i,1,n-2){
				F(j,0,n-1)if(!vis[j]&&qry(Arr{p},Arr{j})){
					p=j,ret.pb(p),vis[p]=1;
					break;
				}
			}
			int q=0;
			while(vis[q])++q;
			if(qry(Arr{p},Arr{q}))
				return ret.pb(q),ret;
			return reverse(ret.begin(),ret.end()),ret.pb(q),ret;
		}
	}
	namespace D1{
		bool vis[N];
		Arr main(){
			F(i,0,n)vis[i]=0;
			int p=0;
			Arr ret;ret.pb(p),vis[p]=1;
			F(i,1,n-1){
				bool flag=0;
				F(j,0,n-1)if(!vis[j]&&qry(Arr{p},Arr{j})){
					p=j,ret.pb(p),vis[p]=1,flag=1;
					break;
				}
				if(!flag)break;
			}
//			CUT;
//			dbg("ret:");
//			for(int x:ret)dbg("%d ",x);
//			dbg("\n");
//			dbg("vis:");
//			F(i,0,n-1)if(!vis[i])dbg("%d ",i);
//			dbg("\n");
//			CUT;
			if((int)ret.size()>n/2)return ret;
			ret.clear();
			F(i,0,n-1)if(!vis[i])ret.pb(i);
			return ret;
		}
	}
	Arr main(){
		return d==3?D3::main()
		:(d==2?D2::main():D1::main());
	}
}
std::vector<int> longest_trip(int N, int D)
{
    SOL::n=N,SOL::d=D;
    return SOL::main();
}