#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(S.size()>T.size()) return S;
        return T;
}