#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define vec vector
#define deq deque
#define conn are_connected
#define ff front
#define bb back
#define V int
#pragma optimize("", on)

void conc(deq<V> &l1, deq<V> &l2) {
    while (!l2.empty()) {
        l1.pb(l2.bb());
        l2.ppb();
    }
}

void cmb(deq<V> &l1, deq<V> &l2) {
    if (l2.empty()) return;

    if (conn({l1.bb()}, {l2.bb()})) {
        conc(l1, l2);
        return;
    }
    if (conn({l1.bb()}, {l2.ff()})) {
        while (!l2.empty()) {
            l1.pb(l2.ff());
            l2.ppf();
        }
        return;
    }
    if (conn({l1.ff()}, {l2.bb()})) {
        while (!l2.empty()) {
            l1.pf(l2.bb());
            l2.ppb();
        }
        return;
    }
    if (conn({l1.ff()}, {l2.ff()})) {
        while (!l2.empty()) {
            l1.pf(l2.ff());
            l2.ppf();
        }
        return;
    }

    vec<V> l1v(l1.begin(), l1.end()), l2v(l2.begin(), l2.end());

    if (!conn(l1v, l2v)) return;

    V a = 0, b = l2.size() - 1, pos;
    while (a != b) {
        vec<V> v(l2.begin() + a, l2.begin() + (a + b) / 2 + 1);
        if (conn(l1v, v)) b = (a + b) / 2;
        else a = (a + b) / 2 + 1;
    }
    pos = a;

    a = 0, b = l1.size() - 1;
    while (a != b) {
        vec<V> v(l1.begin() + a, l1.begin() + (a + b) / 2 + 1);
        if (conn(v, {l2v[pos]})) b = (a + b) / 2;
        else a = (a + b) / 2 + 1;
    }
    V pos2 = a;

    if (pos2 != l1.size() - 1) rotate(l1.begin(), l1.begin() + pos2 + 1, l1.end());
    if (pos != l2.size() - 1) rotate(l2.begin(), l2.begin() + pos + 1, l2.end());

    conc(l1, l2);
}

vec<V> longest_trip(V N, V) {
    srand(time(0));
    vec<V> id(N);
    for (V i = 0; i < N; i++) id[i] = i;
    random_shuffle(id.begin(), id.end());

    deq<V> l1, l2;
    l1.pb(id[0]), l2.pb(id[1]);
    bool sep = false;

    for (V i = 2; i < N; i++) {
        if (conn({l1.bb()}, {id[i]})) {
            l1.pb(id[i]);
            sep = false;
        } else if (sep) {
            l2.pb(id[i]);
        } else if (conn({l2.bb()}, {id[i]})) {
            l2.pb(id[i]);
            sep = true;
        } else {
            if (i < N - 2) {
                bool c1 = conn({id[i]}, {id[i + 1]});
                bool c2 = conn({id[i]}, {id[i + 2]});
                if (c1 && c2) {
                    conc(l1, l2);
                    l2.pb(id[i + 1]), l2.pb(id[i]), l2.pb(id[i + 2]);
                } else if (!c1 && !c2) {
                    l1.pb(id[i + 1]), l1.pb(id[i + 2]);
                    conc(l1, l2);
                    l2.pb(id[i]);
                } else {
                    if (!c1) l1.pb(id[i + 1]);
                    else l1.pb(id[i + 2]);
                    conc(l1, l2);
                    if (!c1) l2.pb(id[i + 2]);
                    else l2.pb(id[i + 1]);
                    l2.pb(id[i]);
                }
                i += 2;
            } else {
                conc(l1, l2);
                l2.pb(id[i]);
            }
            sep = false;
        }
    }

    if (l1.size() < l2.size()) swap(l1, l2);
    cmb(l1, l2);

    vec<V> ans(l1.begin(), l1.end());
    return ans;
}