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

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

        S.push_back(0);

        bool cond=true;
        for(int i=1;i<N;i++) {
                if(are_connected({S.back()},{i})) {
                        S.push_back(i);
                        cond=false;
                } else {
                        if(T.empty()) {
                                T={i};
                                cond=true;
                                continue;
                        }
                        if(cond) {
                                T.push_back(i);
                        } else {
                                if(are_connected({T.back()},{i})) {
                                        T.push_back(i);
                                        cond=true;
                                } else {
                                        // S back -> .... -> T back
                                        if(i+1<N) {
                                                if(are_connected({i},{i+1})) {
                                                        while(T.size()) {
                                                                S.push_back(T.back());
                                                                T.pop_back();
                                                        }
                                                        T={i,i+1};
                                                } else {
                                                        // S back -> i+1 -> T back
                                                        S.push_back(i+1);
                                                        while(T.size()) {
                                                                S.push_back(T.back());
                                                                T.pop_back();
                                                        }
                                                        T.push_back(i);
                                                        cond=true;
                                                }
                                                i++;
                                        } else {
                                                while(T.size()) {
                                                        S.push_back(T.back());
                                                        T.pop_back();
                                                }
                                                T={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;
        }

}