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



vector<vector<int>> memo;

int point_query(int a, int b){
    if(memo[a][b] != -1) return memo[a][b];
    for(int c = 0; c < memo.size(); c++){
        if(a == c) continue;
        if(b == c) continue;
        if(memo[a][c] == 0 && memo[b][c] == 0)
            return memo[a][b] = memo[b][a] = 1;
    }
    return memo[a][b] = memo[b][a] = are_connected({a}, {b});
}


bool merge_paths(vector<int> p1, vector<int> p2, vector<int> &path){
    if(p1.size() < p2.size()) swap(p1, p2);
    int a = p1[0], b = p1.back();
    int c = p2[0], d = p2.back();
    vector<int> ends_p1, ends_p2;
    if(a == b) ends_p1 = {a};
    else ends_p1 = {a,b};
    if(c == d) ends_p2 = {c};
    else ends_p2 = {c,d};
    if(!are_connected(ends_p1, ends_p2)) return false;
    if(point_query(a, d)){
        path = p2;
        path.insert(path.end(), p1.begin(), p1.end());
        return true;
    }
    if(point_query(b, d)){
        path = p1;
        path.insert(path.end(), p2.rbegin(), p2.rend());
        return true;
    }
    reverse(p2.begin(), p2.end());

    d = p2.back();
    if(point_query(a, d)){
        path = p2;
        path.insert(path.end(), p1.begin(), p1.end());
        return true;
    }
    return false;
}
bool merge_cycles(vector<int> c1, vector<int> c2, vector<int> &path){
    using pii = pair<int, int>;
    int a, b;
    {
        vector<int> x = c1, y = c2;
        while(x.size() != 1 || y.size() != 1){
            if(x.size() > y.size()) swap(x, y);
            if(x.size() == 1){
                int mid = y.size() / 2;
                vector<int> ly(y.begin(), y.begin() + mid);
                vector<int> ry(y.begin() + mid, y.end());
                if(are_connected(x, ly)) y = ly;
                else y = ry;
                continue;
            }  
            int mid = y.size() / 2;
            vector<int> ly(y.begin(), y.begin() + mid);
            vector<int> ry(y.begin() + mid, y.end());
            mid = x.size() / 2;
            vector<int> lx(x.begin(), x.begin() + mid);
            vector<int> rx(x.begin() + mid, x.end());
            if(are_connected(lx, ly)) tie(x, y) = {lx, ly};
            else if(are_connected(lx, ry)) tie(x, y) = {lx, ry};
            else if(are_connected(rx, ly)) tie(x, y) = {rx, ly};
            else tie(x, y) = {rx, ry};
        }
    }
    int n = c1.size(), m = c2.size();
    int x, y;
    tie(x, y) = {a,b};
    for(a = 0; a<n; a++) if(c1[a] == x) break;
    for(b = 0; b<m; b++) if(c2[b] == y) break;

    for(int i = (a + 1) % n; i != a; i = (i+1)%n) path.push_back(c1[i]);
    path.push_back(c1[a]);
    path.push_back(c2[b]);
    for(int i = (b + 1) % m; i != b; i = (i+1)%m) path.push_back(c2[i]);
    return true;
}

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){ 
        memo = vector<vector<int>>(N, vector<int>(N, -1));
        vector<vector<int>> ans = {{0}, {1}};
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
        vector<int> vert(N-2); iota(vert.begin(), vert.end(), 2);
        shuffle(vert.begin(), vert.end(), rng);
        for(int v : vert){
            int a = ans[0].back();
            int b = ans[1].back();
            if(point_query(a, v)){
                ans[0].push_back(v);
            } else if(point_query(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(!are_connected(ans[0], ans[1])){
            if(ans[0].size() > ans[1].size()) return ans[0];
                return ans[1];
        }
            
        if(merge_paths(ans[0], ans[1], path))
            return path;
        if(merge_cycles(ans[0], ans[1], path))
            return path;
        
    }
    return {};
}