#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);
        T.push_back(1);

        for(int i=2;i<N;i++) {
                int p=are_connected({i},{S.back()});
                int q=are_connected({i},{T.back()});

                if(!p && !q) {
                        while(T.size()) {
                                S.push_back(T.back());
                                T.pop_back();
                        }
                        T.push_back(i);
                } else if(!p && q) {
                        T.push_back(i);
                } else if(p && !q) {
                        S.push_back(i);
                } else {
                        S.push_back(i);
                        while(T.size()) {
                                S.push_back(T.back());
                                T.pop_back();
                        }
                }
        }

        if(T.empty()) return S;

        if(!are_connected(S,T)) {
                if(S.size()<T.size()) swap(S,T);
                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(are_connected({res0},{T.front()})) {
                
        } else if(are_connected({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({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;
        }

}