#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

int find(int x, vector<int> a) {
    if (a.size() == 1) {
        return a[0];
    }

    int mid = a.size() / 2;
    if (are_connected({x}, vector<int>(a.begin(), a.begin() + mid))) {
        return find(x, vector<int>(a.begin(), a.begin() + mid));
    }
    return find(x, vector<int>(a.begin() + mid, a.end()));
}

vector<int> longest_trip(int n, int d) {
    vector<int> p(n);
    for (int i = 0; i != n; i++) {
        p[i] = i;
    }

    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(p.begin(), p.end(), rnd);

    int o;
    vector<int> path, gu;
    if (are_connected({p[0]}, {p[1]})) {
        o = 0;
        path = vector<int>{p[0], p[1]};
    } else {
        o = 1;
        path = vector<int>{p[0]};
        gu = vector<int>{p[1]};
    }

    int lk = -1;

    int a = 0, b = 0;

    for (int t = 2; t != n; t++) {
        int x = p[t];
        if (o == 1) {
            if (path.size() > gu.size()) {
                swap(path, gu);
            }
            if (are_connected(path, {x})) {
                if (are_connected(gu, {x})) {
                    if (!are_connected({x}, {path.back()})) {
                        swap(path, gu);
                    }
                    int y = find(x, gu);
                    o = 2;
                    path.push_back(x);
                    gu.erase(find(gu.begin(), gu.end(), y));
                    path.push_back(y);
                    path.insert(path.end(), gu.begin(), gu.end());
                } else {
                    path.push_back(x);
                }
            } else {
                gu.push_back(x);
            }
            lk = -1;
            continue;
        }

        if (are_connected({x}, {path.back()})) {
            path.push_back(x);
            a++;
            lk = -1;
            continue;
        }

        if ((lk == 0) || are_connected({x}, {path[0]})) {
            path.insert(path.begin(), x);
            b++;
            lk = 0;
            continue;
        }

        if (o == 0 && !are_connected({x}, path)) {
            o = 1;
            gu = vector<int>{x};
            continue;
        }

        o = 2;

        gu = path;
        gu.pop_back();
        gu.erase(gu.begin());
        shuffle(gu.begin(), gu.end(), rnd);
        int y = find(x, gu);

        while (path.back() != y) {
            path.insert(path.begin(), path.back());
            path.pop_back();
        }

        path.push_back(x);

        lk = -1;
    }

    if (o == 1) {
        if (path.size() < gu.size()) {
            swap(path, gu);
        }
    }
    return path;
}