#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

bool check(int x,int y)
{
	vector <int> a;
	a.push_back(x);
	vector <int> b;
	b.push_back(y);
	return are_connected(a,b);
}

vector<int> longest_trip(int N, int D)
{
	if(D==3)
	{
		vector <int> ans;
		for(int i=0;i<N;i++)
			ans.push_back(i);
		return ans;
	}

	if(D==2)
	{
		vector <int> ans;
		if(check(0,1) && check(1,2))
			ans.push_back(0), ans.push_back(1), ans.push_back(2);
		else if(check(0,2) && check(2,1))
			ans.push_back(0), ans.push_back(2), ans.push_back(1);
		else
			ans.push_back(1), ans.push_back(0), ans.push_back(2);

		for(int i=3;i<N;i++)
			if(check(i,ans[0]))
				ans.insert(ans.begin(),i);
			else
				ans.insert(ans.end(),i);
		return ans;
	}

	if(D==1)
	{
		vector <int> a,b;
		for(int i=0;i<N;i++)
		{
			if(a.size()==0)
			{
				a.push_back(i);
				continue;
			}

			if(b.size()==0)
			{
				b.push_back(i);
				continue;
			}

			if(check(a[a.size()-1],b[b.size()-1]))
			{
				for(int i=b.size()-1;i>=0;i--)
					a.push_back(b[i]);
				b.clear();
				b.push_back(i);
				continue;
			}

			if(check(a[a.size()-1],i))
				a.push_back(i);
			else
				b.push_back(i);
		}

		if(a.size()<b.size())
			return b;
		return a;
	}
}