#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long 
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;

bool are_connected(vi A, vi B);

mt19937_64 orz;
vi longest_trip(int N, int D) {
	vi a, b;
	L(i, 0, N - 1) {
		if(orz() & 1) {
			swap(a, b);
		}
		if(!sz(a)) {
			a.emplace_back(i);
		} else if(!sz(b)) {
			b.emplace_back(i);
		} else 
		if(are_connected(vi{i}, vi{a.back()})) {
			a.emplace_back(i);
		} else if(are_connected(vi{i}, vi{b.back()})) {
			b.emplace_back(i);
		} else {
			reverse(b.begin(), b.end());
			for(auto&x : b) a.emplace_back(x);
			b.clear();
		}
	}
	L(i, 0, sz(a) - 2) assert(are_connected(vi{a[i]}, vi{a[i + 1]}));
	L(i, 0, sz(b) - 2) assert(are_connected(vi{b[i]}, vi{b[i + 1]}));
	if(sz(a) < sz(b)) {
		swap(a, b);
	}
	if(!are_connected(a, b) || !sz(a) || !sz(b)) {
		return sz(a) > sz(b) ? a : b;
	}
	vi q1 = vi{a[0], a.back()}, q2 = vi{b[0], b.back()};
	if(q1.back() == q1[0]) q1.pop_back();
	if(q2.back() == q2[0]) q2.pop_back();
	if(are_connected(q1, q2)) {
		for(int x : q1) 
			for(int y : q2) if(are_connected(vi{x}, vi{y})) {
				if(x == a.back()) reverse(a.begin(), a.end());
				if(y == b.back()) reverse(b.begin(), b.end());
				reverse(a.begin(), a.end());
				for(auto&x : b) a.emplace_back(x);
				return a;
			}
		return vi{};
	}
	
	int l = 0, r = sz(a) - 1, ans1 = -1, ans2 = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		vi P;
		L(i, 0, mid) P.emplace_back(a[i]);
		if(are_connected(P, b)) {
			ans1 = mid, r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	l = 0, r = sz(b) - 1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		vi P;
		L(i, 0, mid) P.emplace_back(b[i]);
		if(are_connected(vi{a[ans1]}, P)) {
			ans2 = mid, r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	
	vi ans;
	R(i, ans1 - 1, 0) ans.emplace_back(a[i]);
	R(i, sz(a) - 1, ans1) ans.emplace_back(a[i]);
	L(i, ans2, sz(b) - 1) ans.emplace_back(b[i]);
	L(i, 0, ans2 - 1) ans.emplace_back(b[i]);
	return ans; 
}