#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();
        }
    }
    // if (!ans2.empty()) {
    //     if (are_connected(ans1, ans2)) {
    //         int l = 0, r = ans1.size();
    //         while (l < r - 1) {
    //             int m = (l + r) / 2;
    //             if (are_connected(vector<int>(ans1.begin() + l, ans1.begin() + m), 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;
}