#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "longesttrip.h"

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi2,fma")


#ifdef lisie_bimbi
#define debug(x) cout << #x << " : " << x << endl;
#else
#define debug(x) ;
#define endl '\n'
#endif

//#define int long long
#define inf 1000000000000000000
#define double long double
typedef long long ll;
vector<vector<int>> mas;
vector<vector<int>> v;
vector<int> per;

bool get(int a, int b){
    a = per[a];
    b = per[b];
    if(v[a][b] != -1){
        return v[a][b];
    }
    if(a == b){
        return 0;
    }
    if(are_connected({a}, {b})){
        v[a][b] = 1;
        v[b][a] = 1;
    }else{
        v[a][b] = 0;
        v[b][a] = 0;
    }
    return v[a][b];
}

void dfs(int u, vector<int> &used, int x, int &cnt){
    used[u] = 1;
    cnt++;
    for(int i = 0; i <= x; i++){
        if(!used[i] && get(u, i)){
            dfs(i, used, x, cnt);
        }
    }
}

deque<int> solve(int n){
    if(n == 2) {
        return {0, 1};
    }
    vector<int> used(n);
    int cnt = 0;
    dfs(0, used, n - 2, cnt);
    if(cnt == n - 1){
        deque<int> ans = solve(n - 1);
        if(get(n - 1, ans[0])){
            ans.push_front(n - 1);
            return ans;
        }else if(get(n - 1, ans.back())){
            ans.push_back(n - 1);
            return ans;
        }else{
            deque<int> ans1;
            int ind = -1;
            for(int i = 0; i < n - 1; i++){
                if(get(ans[i], n - 1)){
                    ind = i;
                    break;
                }
            }
            ans1.push_back(n - 1);
            for(int i = ind; i < n - 1; i++){
                ans1.push_back(ans[i]);
            }
            for(int i = 0; i < ind; i++){
                ans1.push_back(ans[i]);
            }
            return ans1;
        }
    }else{
        deque<int> ans;
        int a, b;
        for(int i = 0; i < n - 1; i++){
            if(used[i]) {
                if (get(i, n - 1)){
                    a = i;
                }
            }else {
                if (get(i, n - 1)) {
                    b = i;
                }
            }
        }
        for(int i = 0; i < n - 1; i++){
            if(used[i] && (i != a)){
                ans.push_back(i);
            }
        }
        ans.push_back(a);
        ans.push_back(n - 1);
        ans.push_back(b);
        for(int i = 0; i < n - 1; i++){
            if(!used[i] && (i != b)){
                ans.push_back(i);
            }
        }
        return ans;
    }
}

mt19937 rnd(239);

vector<int> longest_trip(int n, int d){
    per.resize(n);
    for(int i = 0; i < n; i++){
        per[i] = i;
    }
    std::shuffle(per.begin(), per.end(), rnd);
    if(d == 3){
        vector<int> ans(n);
        for(int i = 0; i < n; i++){
            ans[i] = i;
        }
        return ans;
    }else if(d == 2){
        deque<int> ans;
        int x;
        if(are_connected({0}, {1})){
            x = 1;
            ans = {0, 1};
        }else{
            ans = {0, 2};
            x = 2;
        }
        for(int i = 1; i < n; i++){
            if(i == x){
                continue;
            }
            if(are_connected({i}, {ans.back()})){
                ans.push_back(i);
            }else{
                ans.push_front(i);
            }
        }
        vector<int> ans1;
        for(auto i : ans){
            ans1.push_back(i);
        }
        return ans1;
    }
    v.resize(n, vector<int>(n, -1));
    vector<int> used(n, 0);
    int cnt = 0;
    dfs(0, used, n - 1, cnt);
    if(cnt != n){
        if(cnt * 2 >= n){
            vector<int> ans;
            for(int i = 0; i < n; i++){
                if(used[i]){
                    ans.push_back(i);
                }
            }
            return ans;
        }else{
            vector<int> ans;
            for(int i = 0; i < n; i++){
                if(!used[i]){
                    ans.push_back(i);
                }
            }
            return ans;
        }
    }
    auto ans = solve(n);
    vector<int> ans1;
    for(auto i : ans){
        ans1.push_back(i);
    }
    return ans1;
}