#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()
std::vector<int> longest_trip(int N, int D)
{
	int pos = 0;
	vector <int> ans = {0};
	for(int i = 1;i < N;i++){
		bool res = are_connected({pos}, {i});
		if(res) ans.pb(i);
		else if(i + 1 < N){
			ans.pb(i + 1);
			ans.pb(i);
			i++;
		}
		pos = ans.back();
	}
	if(sz(ans) < N) {
		reverse(all(ans));
		ans.pb(N - 1);
	}
	return ans;
}