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


bool merge_paths(vector<int> p1, vector<int> p2, vector<int> &path){
    int a = p1[0], b = p1.back();
    int d = p2.back();
    if(are_connected({a}, {d})){
        path = p2;
        path.insert(path.end(), p1.begin(), p1.end());
        return true;
    }
    if(are_connected({b}, {d})){
        path = p1;
        path.insert(path.end(), p2.rbegin(), p2.rend());
        return true;
    }
    reverse(p2.begin(), p2.end());

    d = p2.back();
    if(are_connected({a}, {d})){
        path = p2;
        path.insert(path.end(), p1.begin(), p1.end());
        return true;
    }
    if(are_connected({b}, {d})){
        path = p1;
        path.insert(path.end(), p2.rbegin(), p2.rend());
        return true;
    }
    return false;
}

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(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};
            }          
        }
        vector<int> path;
        if(merge_paths(ans[0], ans[1], path))
            return path;
        int a = -1, b = -1;
        int n = ans[0].size(), m = ans[1].size();
        for(int i = 0 ; i < n; i++)
            for(int j = 0 ; j < m; j++)
                if(are_connected({ans[0][i]}, {ans[1][j]})){
                    a = i, b = j;
                    break;
                }
        if(a == -1){
            if(ans[0].size() > ans[1].size()) return ans[0];
            else return ans[1];
        }
        for(int i = (a + 1) % n; i != a; i = (i+1)%n) path.push_back(ans[0][i]);
        path.push_back(ans[0][a]);
        path.push_back(ans[1][b]);
        for(int i = (b + 1) % m; i != b; i = (i+1)%m) path.push_back(ans[1][i]);
        return path;
    }
    return {};
}