#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);
}