#include <iostream>
#include <cstdio>
#include <algorithm>
#include <random>
#include <vector>
#include "longesttrip.h"
using namespace std;
mt19937 rnd(114514);
vector<int> make_vec(int x){
    vector<int> ans;
    ans.push_back(x);
    return ans;
}
pair<int,int> find(vector<int> a,vector<int> b){
    if (a.size()==1&&b.size()==1)return make_pair(0,0);
    int o=0;
    if (a.size()<b.size())swap(a,b),o=1;
    int la=a.size();
    vector<int> al,ar;
    for (int i=0;i<la/2;i++)al.push_back(a[i]);
    for (int i=la/2;i<la;i++)ar.push_back(a[i]);
    pair<int,int> ans;
    if (are_connected(al,b))ans=find(al,b);
    else ans=find(ar,b),ans.first+=la/2;
    if (o==1)swap(ans.first,ans.second);
    return ans;
}
vector<int> work(vector<vector<int>> c){
    int l=(int)c.size();
    if (l==1)return c[0];
    if (l==2){
        if (are_connected(c[0],c[1])){
            int l0=c[0].size(),l1=c[1].size();
            vector<int> ans;
            if (are_connected(make_vec(c[0][0]),make_vec(c[1][0]))){
                for (int i=l1-1;i>=0;i--)ans.push_back(c[1][i]);
                for (int i=0;i<l0;i++)ans.push_back(c[0][i]);
                return ans;
            }
            else if (are_connected(make_vec(c[0][0]),make_vec(c[1][l1-1]))){
                for (int i=0;i<l1;i++)ans.push_back(c[1][i]);
                for (int i=0;i<l0;i++)ans.push_back(c[0][i]);
                return ans;
            }
            swap(c[0],c[1]);
            swap(l0,l1);
            if (are_connected(make_vec(c[0][0]),make_vec(c[1][0]))){
                for (int i=l1-1;i>=0;i--)ans.push_back(c[1][i]);
                for (int i=0;i<l0;i++)ans.push_back(c[0][i]);
                return ans;
            }
            else if (are_connected(make_vec(c[0][0]),make_vec(c[1][l1-1]))){
                for (int i=0;i<l1;i++)ans.push_back(c[1][i]);
                for (int i=0;i<l0;i++)ans.push_back(c[0][i]);
                return ans;
            }
            pair<int,int> qwq=find(c[0],c[1]);
            int x=qwq.first,y=qwq.second;
            for (int i=1;i<=l0;i++)ans.push_back(c[0][(x+i)%l0]);
            for (int i=0;i<l1;i++)ans.push_back(c[1][(y+i)%l1]);
            return ans;
        }
        else{
            if (c[0].size()>c[1].size())return c[0];
            return c[1];
        }
    }
    vector<vector<int>> qwq(l);
    int o=0;
    for (int i=0;i<l;i++){
        qwq[i]=c[i];
        if (i>0){
            if (are_connected(make_vec(qwq[i-1][0]),make_vec(qwq[i][0]))){
                vector<int> ovo;
                for (int j=(int)qwq[i-1].size()-1;j>=0;j--)ovo.push_back(qwq[i-1][j]);
                for (int j=0;j<(int)qwq[i].size();j++)ovo.push_back(qwq[i][j]);
                qwq[i]=ovo;
                qwq[i-1].clear();
                o=0;
            }
            else{
                if (o==1&&qwq[i-2].size()>0){
                    vector<int> ovo;
                    for (int j=(int)qwq[i-2].size()-1;j>=0;j--)ovo.push_back(qwq[i-2][j]);
                    for (int j=0;j<(int)qwq[i].size();j++)ovo.push_back(qwq[i][j]);
                    qwq[i]=ovo;
                    qwq[i-2].clear();
                    o=0;    
                }
                else o=1;
            }
        }
    }
    vector<vector<int>> awa;
    for (int i=0;i<l;i++)
        if (qwq[i].size()>0)awa.push_back(qwq[i]);
    vector<int> ans=work(awa);
    return ans;
}
vector<int> longest_trip(int n,int d){
    vector<vector<int>> c;
    for (int i=0;i<n;i++)c.push_back(make_vec(i));
    shuffle(c.begin(),c.end(),rnd);
    vector<int> ans=work(c);
    return ans;
}