#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

std::vector<int> longest_trip(int N, int D) {
        vector<int> S,T;

        S.push_back(0);

        for(int i=1;i<N;i++) {
                if(T.size()>S.size()) swap(S,T);
                if(T.size()) if(rng()%2) swap(S,T);

                if(are_connected({S.back()},{i})) {
                        S.push_back(i);
                        if(T.empty()) continue;
                        if(!are_connected({T.back()},{i})) continue;

                        while(T.size()) {
                                S.push_back(T.back());
                                T.pop_back();
                        }
                } else {
                        T.push_back(i);
                }
        } 

        if(S.size()<T.size()) swap(S,T);
        if(T.empty()) return S;

        int l=0,r=S.size()-1,res0=-1,res1=-1;
        while(l<=r) {
                int mid=(l+r)/2;
                vector<int> qry;
                for(int i=0;i<=mid;i++) qry.push_back(S[i]);

                if(are_connected(qry,T)) {
                        res0=mid,r=mid-1;
                } else {
                        l=mid+1;
                }
        }

        if(res0==-1) return S;

        if(are_connected({S[res0]},{T.front()})) {
                
        } else if(are_connected({S[res0]},{T.back()})) {
                reverse(T.begin(),T.end());
        } else {
                l=0,r=T.size()-1;
                while(l<=r) {
                        int mid=(l+r)/2;
                        vector<int> qry;
                        for(int i=0;i<=mid;i++) qry.push_back(T[i]);

                        if(are_connected({S[res0]},qry)) {
                                res1=mid,r=mid-1;
                        } else {
                                l=mid+1;
                        }
                }

                vector<int> nxt;
                for(int i=res1;i>=0;i--) {
                        nxt.push_back(T[i]);
                }
                for(int i=T.size()-1;i>res1;i--) {
                        nxt.push_back(T[i]);
                }
                T=nxt;
        }

        if(are_connected({T.front()},{S.front()})) {
                vector<int> nxt;
                for(int i=S.size()-1;i>=0;i--) nxt.push_back(S[i]);
                for(int i=0;i<T.size();i++) nxt.push_back(T[i]);
                return nxt;
        } else if(are_connected({T.front()},{S.back()})) {
                vector<int> nxt;
                for(int i=0;i<S.size();i++) nxt.push_back(S[i]);
                for(int i=0;i<T.size();i++) nxt.push_back(T[i]);
                return nxt;
        } else {
                vector<int> nxt;
                for(int i=T.size()-1;i>=0;i--) nxt.push_back(T[i]);
                for(int i=res0;i>=0;i--) nxt.push_back(S[i]);
                for(int i=S.size()-1;i>res0;i--) nxt.push_back(S[i]);
                return nxt;
        }

}