#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;
        int start = 3;
        if(are_connected({0}, {1}))
            ans = {0, 1}, start = 2; 
        else
            ans = {0, 2, 1};
        
        for(int v = start; v < N; v++){
            if(are_connected({ans.front()}, {v})) ans.push_front(v);
            else ans.push_back(v);
        }
        return {ans.begin(), ans.end()};
    }
    if(false && D == 1){
        vector<vector<int>> ans = {{0}, {1}};
        for(int v = 2; v < N; v++){
            int a = ans[0].back();
            int b = ans[1].back();
            if(are_connected({a}, {v})){
                ans[0].push_back(v);
            } else if(are_connected({b}, {v}))
                ans[1].push_back(v);
            else{
                ans[0].insert(ans[0].end(), ans[1].rbegin(), ans[1].rend());
                ans[1] = {v};
            }          
        }
        if(ans[0].size() > ans[1].size()) return ans[0];
        else return ans[1];
    }
    if(D == 1){
        vector<vector<int>> ans = {{0}};
        for(int v = 2; v < N; v++){
            if(ans.size() == 1){
                if(are_connected({ans[0].back()}, {v})) ans[0].push_back(v);
                else ans.push_back({v});
            } else {
                bool a = are_connected({ans[0].back()}, {v});
                bool b = are_connected({ans[1].back()}, {v});
                if(a && b){
                    ans[0].push_back(v);
                    ans[0].insert(ans[0].end(), ans[1].rbegin(), ans[1].rend());
                    ans.pop_back();
                } else if(!a && !b){
                    ans[0].insert(ans[0].end(), ans[1].rbegin(), ans[1].rend());
                    ans[1] = {v};
                } else if(a){
                    ans[0].push_back(v);
                } else{
                    ans[1].push_back(v);
                }
            }    
        }
        if(ans.size() == 1) return ans[0];
        // if(are_connected({ans[0][0]}, {ans[1][0]})){
        //     reverse(ans[0].begin(), ans[0].end());
        //     ans[0].insert(ans[0].end(), ans[1].begin(), ans[1].end());
        //     return ans[0];
        // }
        // if(are_connected({ans[0][0]}, {ans[1].back()})){
        //     ans[1].insert(ans[1].end(), ans[0].begin(), ans[0].end());
        //     return ans[1];
        // }

        if(ans[0].size() > ans[1].size()) return ans[0];
        else return ans[1];
    }
    return {};
}