#include <bits/stdc++.h>

#include "longesttrip.h"

using namespace std;

vector<int> longest_trip(int n, int d) {
    mt19937 rnd(57);
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    shuffle(ord.begin(), ord.end(), rnd);
    vector<int> ans1, ans2;
    bool disconnected = false;
    for (int i = 0; i < n; ++i) {
        if (ans1.empty() || are_connected({ans1.back()}, {ord[i]})) {
            ans1.push_back(ord[i]);
            disconnected = false;
        } else if (disconnected) {
            ans2.push_back(ord[i]);
        } else if (ans2.empty() || are_connected({ans2.back()}, {ord[i]})) {
            ans2.push_back(ord[i]);
            disconnected = true;
        } else {
            if (i == n - 1) {
                reverse(ans2.begin(), ans2.end());
                for (auto vl : ans2) {
                    ans1.push_back(vl);
                }
                ans2 = {ord[i]};
            } else {
                if (are_connected({ord[i]}, {ord[i + 1]})) {
                    reverse(ans2.begin(), ans2.end());
                    for (auto vl : ans2) {
                        ans1.push_back(vl);
                    }
                    ans2 = {ord[i], ord[i + 1]};
                } else {
                    ans1.push_back(ord[i + 1]);
                    reverse(ans2.begin(), ans2.end());
                    for (auto vl : ans2) {
                        ans1.push_back(vl);
                    }
                    ans2 = {ord[i]};
                }
                disconnected = false;
                ++i;
            }
        }
    }
    if (ans1.size() < ans2.size()) {
        swap(ans1, ans2);
    }
    auto try_to_add = [&](int last, vector<int> vals) {
        if (vals.empty()) {
            return -1;
        }
        if (!are_connected({last}, vals)) {
            return -1;
        }
        while (vals.size() > 1) {
            int m = vals.size() / 2;
            vector<int> vals1, vals2;
            for (int i = 0; i < (int)vals.size(); ++i) {
                if (i < m) {
                    vals1.push_back(vals[i]);
                } else {
                    vals2.push_back(vals[i]);
                }
            }
            if (are_connected({last}, vals1)) {
                vals = vals1;
            } else {
                vals = vals2;
            }
        }
        return vals[0];
    };
    if (!ans2.empty()) {
        if (are_connected({ans1.back()}, {ans2.back()})) {
            reverse(ans2.begin(), ans2.end());
            for (auto vl : ans2) {
                ans1.push_back(vl);
            }
            ans2.clear();
        } else if (are_connected({ans1.back()}, {ans2[0]})) {
            for (auto vl : ans2) {
                ans1.push_back(vl);
            }
            ans2.clear();
        } else if (are_connected({ans1[0]}, {ans2.back()})) {
            reverse(ans1.begin(), ans1.end());
            reverse(ans2.begin(), ans2.end());
            for (auto vl : ans2) {
                ans1.push_back(vl);
            }
            ans2.clear();
        } else if (are_connected({ans1[0]}, {ans2[0]})) {
            reverse(ans1.begin(), ans1.end());
            for (auto vl : ans2) {
                ans1.push_back(vl);
            }
            ans2.clear();
        }
    }
    if (!ans2.empty()) {
        if (are_connected(ans1, ans2)) {
            int l = 0, r = ans1.size();
            while (l < r - 1) {
                int m = (l + r) / 2;
                vector<int> nw;
                for (int i = l; i < m; ++i) {
                    nw.push_back(ans1[i]);
                }
                if (are_connected(nw, ans2)) {
                    r = m;
                } else {
                    l = m;
                }
            }
            vector<int> ll, rr;
            for (auto vl : ans1) {
                if (ll.empty() || ll.back() != ans1[l]) {
                    ll.push_back(vl);
                } else {
                    rr.push_back(vl);
                }
            }
            ans1.clear();
            for (auto vl : rr) {
                ans1.push_back(vl);
            }
            for (auto vl : ll) {
                ans1.push_back(vl);
            }
            int val = try_to_add(ans1.back(), ans2);
            if (val != -1) {
                ll.clear(), rr.clear();
                for (auto vl : ans2) {
                    if (rr.empty() && vl != val) {
                        ll.push_back(vl);
                    } else {
                        rr.push_back(vl);
                    }
                }
                for (auto vl : rr) {
                    ans1.push_back(vl);
                }
                for (auto vl : ll) {
                    ans1.push_back(vl);
                }
                ans2.clear();
            }
        }
    }
    return ans1;
}