#include <bits/stdc++.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;
}

answer.code: In function ‘void cmb(std::deque<int>&, std::deque<int>&)’:
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:25:9: note: in expansion of macro ‘conn’
   25 |     if (conn({l1.bb()}, {l2.bb()})) {
      |         ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:29:9: note: in expansion of macro ‘conn’
   29 |     if (conn({l1.bb()}, {l2.ff()})) {
      |         ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:36:9: note: in expansion of macro ‘conn’
   36 |     if (conn({l1.ff()}, {l2.bb()})) {
      |         ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:43:9: note: in expansion of macro ‘conn’
   43 |     if (conn({l1.ff()}, {l2.ff()})) {
      |         ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:53:10: note: in expansion of macro ‘conn’
   53 |     if (!conn(l1v, l2v)) return;
      |          ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:58:13: note: in expansion of macro ‘conn’
   58 |         if (conn(l1v, v)) b = (a + b) / 2;
      |             ^~~~
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:66:13: note: in expansion of macro ‘conn’
   66 |         if (conn(v, {l2v[pos]})) b = (a + b) / 2;
      |             ^~~~
answer.code: In function ‘std::vector<int> longest_trip(int, int)’:
answer.code:9:14: error: ‘are_connected’ was not declared in this scope
    9 | #define conn are_connected
      |              ^~~~~~~~~~~~~
answer.code:88:13: note: in expansion of macro ‘conn’
   88 |         if (conn({l1.bb()}, {id[i]})) {
      |             ^~~~