#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;
    queue<vector<int>> ls;
    forn(i,n) ls.push({i});
    while (sz(ls) > 2) {
        vector<int> a = ls.front();
        ls.pop();
        vector<int> b = ls.front();
        ls.pop();
        vector<int> c = ls.front();
        ls.pop();
        if (are_connected({a.back()}, {b.back()})) {
            reverse(all(b));
            for (int i : b) a.pb(i);
            ls.push(a);
            ls.push(c);
            continue;
        }
        if (are_connected({a.back()}, {c.back()})) {
            reverse(all(c));
            for (int i : c) a.pb(i);
            ls.push(a);
            ls.push(b);
            continue;
        }
        reverse(all(c));
        for (int i : c) b.pb(i);
        ls.push(b);
        ls.push(a);
    }
    auto v1 = ls.front();
    ls.pop();
    auto v2 = ls.front();
    ls.pop();
    if (!are_connected(v1, v2)) {
        if (sz(v1) < sz(v2)) swap(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;
}