#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
int n, m, k, qq;
void merge(deque<int> &a, deque<int> &b) {
    while (!b.empty()) {
        a.push_back(b.back());
        b.pop_back();
    }    
}

std::vector<int> longest_trip(int N, int D) {
    deque<int> a, b;
    a.push_back(0);
    b.push_back(1);
    for (int i = 2; i < N; i += 2) {
        if (i == N - 1) {
            bool A = are_connected({a.back()}, {i});
            bool B = are_connected({b.back()}, {i});
            if (A) a.push_back(i);
            else if (B) b.push_back(i);
            else merge(a, b), b.push_back(i);
        }
        
        else if (are_connected({i}, {i + 1})) {
            bool A = are_connected({a.back()}, {i});
            bool B = are_connected({b.back()}, {i});
            if (A) a.push_back(i), a.push_back(i + 1);
            else if (B) b.push_back(i), b.push_back(i + 1);
            else {
                merge(a, b);
                b.push_back(i), b.push_back(i + 1);
            }
        }
        
        else {
            int x;
            if (are_connected({i}, {a.back()})) a.push_back(i), x = i + 1;
            else a.push_back(i + 1), x = i;
            if (are_connected({b.back()}, {x})) b.push_back(x);
            else merge(a, b), b.push_back(x);
        }
    }
    
    int sa = a.size(), sb = b.size();
    vector<int> av(sa), bv(sb);
    for (int i = 0; i < sa; i++) av[i] = a[i];
    for (int i = 0; i < sb; i++) bv[i] = b[i];
    if (!are_connected(av, bv)) {
        return (sa < sb ? bv : av);
    }
    
    vector<int> qa = {av[0], av[sa - 1]}, qb = {bv[0], bv[sb - 1]};
    if (sa == 1) qa.pop_back();
    if (sb == 1) qb.pop_back();
    if (are_connected(qa, qb)) {
        for (int i = 0; i < qa.size(); i++) {
            for (int j = 0; j < qb.size(); j++) {
                int u = qa[i], v = qb[j];
                if (are_connected({u}, {v})) {
                    if (!i) reverse(av.begin(), av.end());
                    if (j) reverse(bv.begin(), bv.end());
                    break;
                }
            }
        }
    }
    
    else {
        int l = 0, r = sa - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            vector<int> c;
            for (int i = l; i <= mid; i++) c.push_back(av[i]);
            if (are_connected(bv, c)) r = mid;
            else l = mid + 1;
        }
        
        int pa = l;
        l = 0, r = sb - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            vector<int> c;
            for (int i = l; i <= mid; i++) c.push_back(bv[i]);
            if (are_connected({av[pa]}, c)) r = mid;
            else l = mid + 1;
        }
        
        int pb = l;
        rotate(av.begin(), av.begin() + pa + 1, av.end());
        rotate(bv.begin(), bv.begin() + pb, bv.end());
    }
    
    for (int x : bv) av.push_back(x);
    return av;
}