#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
already knew the solution
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "longesttrip.h"
std::vector<int> longest_trip(int n, int d)
{
vector<deque<int>> paths;
rep(i,n){
paths.pb({i});
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while(sz(paths) >= 3){
int siz = sz(paths);
vector<int> ord(siz);
rep(i,siz) ord[i] = i;
shuffle(all(ord),rng);
auto p1 = paths[ord[0]];
auto p2 = paths[ord[1]];
auto p3 = paths[ord[2]];
vector<deque<int>> new_paths;
rep(i,siz){
bool ok = true;
rep(j,3){
if(i == ord[j]){
ok = false;
}
}
if(ok){
new_paths.pb(paths[i]);
}
}
int u = p1[0], v = p2[0], w = p3[0];
if(are_connected({u},{v})){
while(!p2.empty()){
p1.push_front(p2.front());
p2.pop_front();
}
}
else if(are_connected({u},{w})){
while(!p3.empty()){
p1.push_front(p3.front());
p3.pop_front();
}
}
else{
while(!p3.empty()){
p2.push_front(p3.front());
p3.pop_front();
}
}
if(!p1.empty()){
new_paths.pb(p1);
}
if(!p2.empty()){
new_paths.pb(p2);
}
if(!p3.empty()){
new_paths.pb(p3);
}
paths = new_paths;
}
auto p1 = paths[0], p2 = paths[1];
if(are_connected({p1[0]},{p2[0]})){
while(!p2.empty()){
p1.push_front(p2.front());
p2.pop_front();
}
}
else if(are_connected({p1[0]},{p2.back()})){
while(!p2.empty()){
p1.push_front(p2.back());
p2.pop_back();
}
}
else if(are_connected({p1.back()},{p2[0]})){
while(!p2.empty()){
p1.pb(p2.front());
p2.pop_front();
}
}
else if(are_connected({p1.back()},{p2.back()})){
while(!p2.empty()){
p1.pb(p2.back());
p2.pop_back();
}
}
if(p2.empty()){
return vector<int>(all(p1));
}
int l = 0, r = sz(p1)-1;
int pos1 = -1;
while(l <= r){
int mid = (l+r) >> 1;
vector<int> v1;
rep(i,mid+1){
v1.pb(p1[i]);
}
vector<int> v2(all(p2));
if(are_connected(v1,v2)){
pos1 = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
if(pos1 == -1){
if(sz(p1) > sz(p2)){
return vector<int>(all(p1));
}
else{
return vector<int>(all(p2));
}
}
l = 0, r = sz(p2)-1;
int pos2 = -1;
while(l <= r){
int mid = (l+r) >> 1;
vector<int> v1 = {p1[pos1]};
vector<int> v2;
rep(i,mid+1){
v2.pb(p2[i]);
}
if(are_connected(v1,v2)){
pos2 = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
assert(pos2 != -1);
rotate(p1.begin(),p1.begin()+pos1,p1.end());
rotate(p2.begin(),p2.begin()+pos2,p2.end());
while(!p2.empty()){
p1.push_front(p2.front());
p2.pop_front();
}
return vector<int>(all(p1));
}
