#include "longesttrip.h"
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define el << '\n'
#define nl cout << '\n'
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define fi first
#define se second
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;

vector<int> longest_trip(int N, int D) {
    int n = N;
    vector<int> v1={0}, v2={1};
    for (int i = 2; i<n-1; i+=2) {
        if (are_connected({i}, {i+1})) {
            if (are_connected({v1.back()}, {i})) {
                v1.pb(i);
                v1.pb(i+1);
            }
            else if (are_connected({v2.back()}, {i})) {
                v2.pb(i);
                v2.pb(i+1);
            }
            else {
                reverse(all(v2));
                for (int j : v2) v1.pb(j);
                v2.clear();
                v2.pb(i);
                v2.pb(i+1);
            }
        }
        else {
            if (are_connected({v1.back()}, {i})) {
                if (are_connected({v2.back()}, {i})) {
                    v1.pb(i);
                    reverse(all(v2));
                    for (int j : v2) v1.pb(j);
                    v2.clear();
                    v2.pb(i+1);
                }
                else {
                    v1.pb(i);
                    v2.pb(i+1);
                }
            }
            else {
                if (are_connected({v2.back()}, {i})) {
                    v1.pb(i+1);
                    v2.pb(i);
                }
                else {
                    v1.pb(i+1);
                    reverse(all(v2));
                    for (int j : v2) v1.pb(j);
                    v2.clear();
                    v2.pb(i);
                }
            }
        }
    }
    if (n%2) {
        if (are_connected({v1.back()}, {n-1})) {
            v1.pb(n-1);
        }
        else if (are_connected({v2.back()}, {n-1})) {
            v2.pb(n-1);
        }
        else {
            reverse(all(v2));
            for (int j : v2) v1.pb(j);
            v2.clear();
            v2.pb(n-1);
        }
    }
    if (sz(v1) < sz(v2)) swap(v1, v2);
    if (!are_connected(v1, v2)) {
        return v1;
    }
    if (!are_connected({v1[0]}, {v1.back()})) {
        if (are_connected({v1[0]}, {v2[0]})) reverse(all(v1));
        for (int i : v2) v1.pb(i);
        return v1;
    }
    if (sz(v2)>1 && !are_connected({v2[0]}, {v2.back()})) {
        if(are_connected({v1[0]}, {v2[0]})) reverse(all(v2));
        for (int i : v1) v2.pb(i);
        return v2;
    }
    int l = 0, h = sz(v1);
    while (h-l > 1) {
        int m = (l+h)/2;
        vector<int> vt;
        forl(i,l,m) vt.pb(v1[i]);
        if (are_connected(vt, v2)) h = m;
        else l = m;
    }
    int i1 = l;
    l = 0; h = sz(v2);
    while (h-l > 1) {
        int m = (l+h)/2;
        vector<int> vt;
        forl(i,l,m) vt.pb(v2[i]);
        if (are_connected({v1[i1]}, vt)) h = m;
        else l = m;
    }
    int i2 = l;
    vector<int> ret;
    forl(i,i1+1,sz(v1)) ret.pb(v1[i]);
    forn(i,i1+1) ret.pb(v1[i]);
    forl(i,i2,sz(v2)) ret.pb(v2[i]);
    forn(i,i2) ret.pb(v2[i]);
    return ret;
}