#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;
    if (a.size()<b.size()) swap(a,b);
    {
        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;
    int x=0;
    for (auto u:p)
    {
        if (a.size()<b.size()) swap(a,b);
        {
            if (!ins(a,u))
            {
                if (x==1)
                {
                    assert(b.empty()||query((poly){b.back()},(poly){u}));
                    b.push_back(u);
                    x=0;
                } else
                {
                    if (!ins(b,u))
                    {
                        reverse(b.begin(),b.end());
                        for (auto v:b) a.push_back(v);
                        b=(poly){u};
                        x=1;
                    } else 
                        x=1;
                }
            } else x=0;
        }   
    }
    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;
}