#include"longesttrip.h"
#include<bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ob pop_back
#define E empty
#define T return
#define B begin
#define C vector
#define W while
#define Q deque
#define S size()
#define ac are_connected
using namespace std;
C<int>longest_trip(int N,int D);
bool ac(C<int>a,C<int>b);
inline C<int> tv(Q<int> x) {T C<int>(x.B(),x.end());}
inline C<int> solve(Q<int>a,Q<int>b)
{
	while(1)
	{
		if(a.S>b.S) swap(a,b);
		if(a.S==0) T tv(b);
		bool x=ac({a.back()},{b.front()}),y=ac({a.back()},{b.back()});
		if(x)
		{
			W(!a.E()) b.pf(a.back()),a.ob();
			T tv(b);
		}
		else if(y)
		{
			W(!a.E()) b.pb(a.back()),a.ob();
			T tv(b);
		}
		if(!ac(tv(a),tv(b))) T tv(b);
		int L=0,R=a.S-1;
		auto V=tv(b);
		W(L<R)
		{
			int M=(L+R)/2;
			ac(C<int>(a.B(),a.B()+M+1),V)?(R=M):(L=M+1);
		}
		int la=L; L=0,R=b.S-1;
		auto U=C<int>(a.B(),a.B()+la+1);
		W(L<R)
		{
			int M=(L+R)/2;
			ac(U,C<int>(b.B(),b.B()+M+1))?(R=M):(L=M+1);
		}
		int lb=L;
		W(lb>0) --lb,b.pb(b.front()),b.pop_front();
		Q<int>d;
		if(la>=(int)a.S/2) W(la>=0) --la,d.pb(a.front()),a.pop_front();
		else {W(la<(int)a.S) d.pf(a.back()),a.ob(); reverse(d.B(),d.end());}
		W(!d.E()) b.pf(d.back()),d.ob();
	}
}
C<int>longest_trip(int N,int D)
{
	C<int>ID(N);
	for(int i=0;i<N;++i) ID[i]=i;
	Q<int>a,b;
	int p=0;
	for(int i=0;i<N;++i)
	{
		int id=ID[i];
		if(a.S<b.S) swap(a,b);
		if(p)
		{
			if(ac({a.back()},{id})) a.pb(id);
			else b.pb(id);
			p=0;
		}
		else
		{
			if(a.E()) {a={id}; continue;}
			if(ac({{a.back()}},{id})) a.pb(id);
			else if(b.E()||ac({b.back()},{id})) b.pb(id),p=1;
			else {W(!a.E()) b.pb(a.back()),a.ob(); a={id};}
		}
	}
	T solve(a,b);
}