#include<bits/stdc++.h>
#include "longesttrip.h"
//#include "grader.cpp"
#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;
    }
    int rsr=query(x,(poly){y});
    if (rsr==0) return 0;
    if (query((poly){x[0]},(poly){y}))
    {
        x.insert(x.begin(),y);
        return 1;
    }
    if (query((poly){x.back()},(poly){y}))
    {
        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 l=1,r=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()]);
    ins1(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(2006100920070217);
    shuffle(p.begin(),p.end(),rnd);
    poly a,b;
    for (auto u:p)
        if (!ins(a,u))
        {
            if (!ins(b,u))
            {
                reverse(b.begin(),b.end());
                for (auto u:b) a.push_back(u);
                b=(poly){u};
            }
        }
    if (query(a,b)==0)
    {
        if (a.size()>b.size()) return a;
        return b;
    }
    a=merge(a,b);
    return a;
}