#include<bits/stdc++.h>
#include "longesttrip.h"
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
// #define N 
using namespace std;
inline int query(poly x,poly y)
{
    if (x.empty()||y.empty()) return 0;
    return are_connected(x,y);
}
bool ins(poly &x,int y)
{
    if (x.empty())
    {
        x.push_back(y);
        return 1;
    }
    if (query((poly){x.back()},(poly){y}))
    {
        x.push_back(y);
        return 1;
    }
    return 0;
}
bool ins1(poly &x,int y,poly b)
{
    if (x.empty())
    {
        x.push_back(y);
        return 1;
    }
    if (query((poly){x[0]},(poly){y}))
    {
        poly ret=b;
        for (auto u:x) ret.push_back(u);
        x=ret;
        return 1;
    }
    if (query((poly){x.back()},(poly){y}))
    {
        poly ret=x;
        reverse(b.begin(),b.end());
        for (auto u:b) x.push_back(u);
        return 1;
    }
    return 0;
}
bool ins2(poly &x,int y,poly b)
{
    if (x.empty())
    {
        x.push_back(y);
        return 1;
    }
    int l=1,r=sz(x)-1;
    int res=r+1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (query(poly(x.begin()+mid,x.end()),(poly){y})==0)
        {
            res=mid;
            r=mid-1;
        } else l=mid+1;
    }
    poly ret=b;
    for (int i=(res-1);i<x.size();i++) ret.push_back(x[i]);
    for (int i=0;i<res-1;i++) ret.push_back(x[i]);
    x=ret;
    return 1;
}
poly merge(poly a,poly b)
{
    if (a.empty()) return b;
    if (b.empty()) return a;
    {
        int res=0;
        poly nxt=b;
        reverse(nxt.begin(),nxt.end());
        if (ins1(a,b[res],nxt)) return a;
    }
    {
        int res=b.size()-1;
        poly nxt;
        for (int i=0;i<b.size();i++)
            nxt.push_back(b[(res+i+1)%b.size()]);
        if (ins1(a,b[res],nxt)) return a;
    }
    int l=1,r=(int)b.size()-1;
    int res=r+1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (query(a,poly(b.begin()+mid,b.end()))==0)
        {
            res=mid;
            r=mid-1;
        } else l=mid+1;
    }
    res--;
    poly nxt;
    for (int i=0;i<b.size();i++)
        nxt.push_back(b[(res+i+1)%b.size()]);
    ins2(a,b[res],nxt);
    return a;
}
std::vector<int> longest_trip(int n, int D)
{
    poly p(n,0);
    for (int i=0;i<n;i++) p[i]=i;
    mt19937_64 rnd(time(0));
    shuffle(p.begin(),p.end(),rnd);
    poly a,b;
    for (auto u:p)
    {
        if (a.size()<b.size()) swap(a,b);
        if (rnd()%2) reverse(a.begin(),a.end());
        if (rnd()%2) reverse(b.begin(),b.end());
        {
            if (!ins(a,u))
            {
                if (!ins(b,u))
                {
                    reverse(b.begin(),b.end());
                    for (auto v:b) a.push_back(v);
                    b=(poly){u};
                }
            }
        }   
    }
    if (query(a,b)==0)
    {
        if (a.size()>b.size()) return a;
        return b;
    }
    // for (int i=0;i<a.size();i++)cout<<a[i]<<",";
    // cout<<endl;
    // for (int i=0;i<b.size();i++)cout<<b[i]<<",";
    // cout<<endl;
    a=merge(a,b);
    // for (int i=0;i<a.size();i++)cout<<a[i]<<",";
    // cout<<endl;
    // for (int i=1;i<a.size();i++) assert(query((poly){a[i-1]},(poly){a[i]}));
    return a;
}