#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;
/*
bool are_connected(vector<int> a, vector<int> b){
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j<  i; j++){
            if(a[i] == a[j]){
                cout << "error1\n";
                cout << 1 / 0;
            }
        }
    }
    for(int i = 0; i < b.size(); i++){
        for(int j = 0; j<  i; j++){
            if(b[i] == b[j]){
                cout << "error2\n";
                cout << 1 / 0;
            }
        }
    }
    for(auto i : a){
        for(auto j : b){
            if(i == j){
                cout << "error3\n";
                cout << 1 / 0;
            }
        }
    }
    for(auto i : a){
        for(auto j : b){
            if(mas[i][j]){
                return 1;
            }
        }
    }
    return 0;
}
*/
void dfs(int u, vector<vector<int>> &v, vector<int> &used, int x, int &cnt){
    used[u] = 1;
    cnt++;
    for(int i = 0; i <= x; i++){
        if(!used[i] && v[u][i]){
            dfs(i, v, used, x, cnt);
        }
    }
}

deque<int> solve(int n, vector<vector<int>> v){
    if(n == 2) {
        return {0, 1};
    }
    vector<int> used(n);
    int cnt = 0;
    dfs(0, v, used, n - 2, cnt);
    if(cnt == n - 1){
        deque<int> ans = solve(n - 1, v);
        if(v[n - 1][ans[0]]){
            ans.push_front(n - 1);
            return ans;
        }else if(v[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(v[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 (v[i][n - 1]){
                    a = i;
                }
            }else {
                if (v[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;
    }
}

vector<int> longest_trip(int n, int d){
    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;
    }
    vector<vector<int>> v(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(are_connected({i}, {j})){
                v[i][j] = 1;
                v[j][i] = 1;
            }
        }
    }
    vector<int> used(n, 0);
    int cnt = 0;
    dfs(0, v, 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, v);
    vector<int> ans1;
    for(auto i : ans){
        ans1.push_back(i);
    }
    return ans1;
}
/*
mt19937 rnd(239);

vector<vector<int>> gengr(int n, int d){
    vector<vector<int>> v(n, vector<int>(n, 1));
    if(d == 3){
        return v;
    }
    for(int ttt = 0; ttt < n * (n - 1) / 2; ttt++){
        int a = rnd() % n;
        int b = rnd() % n;
        if(!v[a][b] || (a == b)){
            continue;
        }
        bool f = 1;
        if(rnd() % 2){
            continue;
        }
        for(int i = 0; i < n; i++){
            if((i == a) || (i == b)){
                continue;
            }
            f = f && ((v[a][i] + v[b][i]) >= d);
        }
        if(f){
            v[a][b] = 0;
            v[b][a] = 0;
        }
    }
    return v;
}

bool check(int n, vector<int> v){
    vector<int> used(n, 0);
    bool f = 1;
    for(int i = 0; i < v.size(); i++){
        f = f && (!used[v[i]]);
        used[v[i]] = 1;
    }
    for(int i = 0; i + 1 < v.size(); i++){
        f = f && are_connected({v[i]}, {v[i + 1]});
    }
    return f;
}


vector<int> now;
vector<int> ans;
void perebor(int n, unordered_set<int> s){
    if(check(n, now)){
        if(now.size() > ans.size()){
            ans = now;
        }
    }
    auto s1 = s;
    for(auto i : s){
        now.push_back(i);
        s1.erase(i);
        perebor(n, s1);
        s1.insert(i);
        now.pop_back();
    }
}

vector<int> mxtrip_cor(int n, int d){
    ans.clear();
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        s.insert(i);
    }
    perebor(n, s);
    return ans;
}

int main(){
    int n = 8;
    int d = 1;
    int t = 0;
    cout << "start\n";
    while(true){
        mas = gengr(n, d);
        vector<int> ans = mxtrip(n, d);
        vector<int> anscor = mxtrip_cor(n, d);
        if(!check(n, ans) || (ans.size() != anscor.size())){
            cout << "AAAAAAAAAAAA\n";
            for(auto i : mas){
                for(auto j : i){
                    cout << j;
                }
                cout << endl;
            }
            cout << "ans:\n";
            for(auto i : ans){
                cout << i << " ";
            }
            cout << endl;
            cout << "anscor:\n";
            for(auto i : anscor){
                cout << i << " ";
            }
            cout << endl;
            return 0;
        }else{
            cout << "ok test: " << t++ << endl;
        }
    }
}
 */