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

const int MX=300;

map<pair<int,int>, int> memo;

bool ask(int a, int b) {
        if(a>b) swap(a,b);
        if(memo.count({a,b})) return memo[{a,b}];
        return memo[{a,b}]=are_connected({a},{b});
}

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

        S.push_back(0);
        T.push_back(1);

        for(int i=2;i<N;i++) {
                V.push_back(i);
        }

        while(V.size()) {
                int i=V.back(); V.pop_back();

                bool p=0,q=0;
                if(S.size()) p=ask(i,S.back());
                if(T.size()) q=ask(i,T.back());

                bool lst=false;
                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);
                        swap(S,T);
                } else {        
                        lst=true;
                        S.push_back(i);
                        while(T.size()) {
                                S.push_back(T.back());
                                T.pop_back();
                        }
                        swap(S,T);
                }

                if(lst) continue;

                for(int i=0,j=S.size()-1;i<=j && T.size()>i;i++,j--) {
                        if(S.size()-i+T.size()<=max(S.size(),T.size())) break;

                        if(ask(S[i],T.back())) {
                                vector<int> nxt;
                                for(int k=S.size()-1;k>=i;k--) {
                                        nxt.push_back(S[k]);
                                }
                                for(int k=T.size()-1;k>=0;k--) {
                                        nxt.push_back(T[k]);
                                }
                                while(S.size()>i) {
                                        S.pop_back();
                                }
                                T=nxt;

                                while(S.size()) {
                                        V.push_back(S.back());
                                        S.pop_back();
                                }
                                break;
                        }

                        if(ask(S[j],T.back())) {
                                vector<int> nxt;

                                for(int k=0;k<=j;k++) {
                                        nxt.push_back(S[k]);
                                }
                                for(int k=T.size()-1;k>=0;k--) {
                                        nxt.push_back(T[k]);
                                }

                                for(int k=j+1;k<S.size();k++) {
                                        V.push_back(S[k]);
                                }
                                T.clear();
                                for(int k=j+1;k<S.size();k++) {
                                        T.push_back(S[k]);
                                }
                                S=nxt;
                                break;
                        }
                }

                if(S.size()<T.size()) swap(S,T);
        }

        return S;
}