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

std::vector<int> longest_trip(int N, int D)
{
    if(D == 3){
        vector<int> ans(N);
        iota(ans.begin(), ans.end(), 0);
        return ans;
    }
    if(D == 2){
        deque<int> ans;
        vector<int> vert(N-2);
        iota(vert.begin(), vert.end(), 3);
        if(are_connected({0}, {1}))
            ans = {0,1}, vert.push_back(2); 
        else
            ans = {0,2}, vert.push_back(1);
        
        for(int v: vert){
            int a = ans.front(), b = ans.back();
            if(are_connected({a}, {v})) ans.push_front(v);
            else ans.push_back(v);
        }
        return vector<int>(ans.begin(), ans.end());
    }
    return {};
}