#include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
bool are_connected(vi A, vi B);
vi longest_trip(int N, int D) {
(void)D;
queue<vi> q;
vi P;
forn(i,N) P.pb(i);
srand(time(0));
random_shuffle(ALL(P));
forn(i,N) q.push({P[i]});
vi a={P[0]}, b;
forsn(i,1,N) {
if(are_connected({a.back()},{P[i]})) {
a.pb(P[i]);
} else if(b.empty() || are_connected({b.back()},{P[i]})) {
b.pb(P[i]);
} else {
reverse(ALL(b));
forn(j,SIZE(b)) a.pb(b[j]);
b={P[i]};
}
}
if(SIZE(b)>SIZE(a)) swap(a,b);
if(b.empty() || !are_connected(a,b)) return a;
vi qa = {a.front()};
if(a.back() != qa.back()) qa.pb(a.back());
vi qb = {b.front()};
if(b.back() != qb.back()) qb.pb(b.back());
if(are_connected(qa, qb)) {
if(are_connected({a.back()}, {b.front()})) {
forn(i,SIZE(b)) a.pb(b[i]);
return a;
}
if(are_connected({b.back()}, {a.front()})) {
forn(i,SIZE(a)) b.pb(a[i]);
return b;
}
if(are_connected({a.front()},{b.front()})) {
reverse(ALL(a));
forn(i,SIZE(b)) a.pb(b[i]);
return a;
}
if(are_connected({a.back()}, {b.back()})) {
reverse(ALL(b));
forn(i,SIZE(b)) a.pb(b[i]);
return a;
}
}
int l=0, r=SIZE(a)-1;
while(l<r) {
int m=(l+r)/2;
if(are_connected(b,vi(a.begin()+l,a.begin()+m+1))) r=m;
else l=m+1;
}
int i=l;
l=0, r=SIZE(b)-1;
while(l<r) {
int m=(l+r)/2;
if(are_connected({a[i]},vi(b.begin()+l,b.begin()+m+1))) r=m;
else l=m+1;
}
int j=l;
vi ans;
forsn(p,j+1,SIZE(b)) ans.pb(b[p]);
forn(p,j+1) ans.pb(b[p]);
forsn(p,i,SIZE(a)) ans.pb(a[p]);
forn(p,i) ans.pb(a[p]);
return ans;
}
