#include "longesttrip.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void merge(vector<int> &a, vector<int> b, bool flag = true) {
    if(flag) reverse(b.begin(), b.end());
    for(auto val : b) a.push_back(val);
}

int binsearch(vector<int> a, vector<int> b) {
    if(b.size() == 1) return b[0];

    vector<int> tophalf, bottomhalf;

    for(int i = 0; i < b.size() / 2; ++i) tophalf.push_back(b[i]);
    for(int i = b.size() / 2; i < b.size(); ++i) bottomhalf.push_back(b[i]);

    if(are_connected(a, tophalf)) return binsearch(a, tophalf);
    return binsearch(a, bottomhalf);
}

vector<int> longest_trip(int n, int d) {
    vector<int> a, b;
    a.push_back(0); b.push_back(1);

    for(int i = 2; i < n; i += 2) {
        if(i + 1 == n) {
            if(are_connected({a.back()}, {i})) a.push_back(i);
            else if(are_connected({b.back()}, {i})) b.push_back(i);
            else {
                merge(a, b); b = {i};
            }
        }
        else {
            if(are_connected({i}, {i + 1})) {
                if(are_connected({a.back()}, {i})) {
                    a.push_back(i); a.push_back(i + 1);
                }
                else if(are_connected({b.back()}, {i})) {
                    b.push_back(i); b.push_back(i + 1);
                }
                else {
                    merge(a, b); b = {i, i + 1};
                }
            }
            else {
                if(are_connected({a.back()}, {i})) a.push_back(i);
                else a.push_back(i + 1);

                if(are_connected({b.back()}, {i})) {
                    if(a.back() == i) {
                        merge(a, b); b = {i + 1};
                    }
                    else b.push_back(i);
                }
                else {
                    if(a.back() == i + 1) {
                        merge(a, b); b = {i};
                    }
                    else b.push_back(i + 1);
                }
            }
        }
    }

    if(!are_connected(a, b)) {
        if(a.size() > b.size()) return a;
        return b;
    }

    for(int i = 0; i < 2; ++i) {
        if (are_connected({a[0]}, {b[0]})) {
            reverse(a.begin(), a.end());
            merge(a, b, false);
            return a;
        }
        if (are_connected({a[0]}, {b.back()})) {
            reverse(a.begin(), a.end());
            merge(a, b);
            return a;
        }
        reverse(a.begin(), a.end()); reverse(b.begin(), b.end());
    }

    int endpoint2 = binsearch(a, b), endpoint1 = binsearch({endpoint2}, a);


    int idx1, idx2;

    for(int i = 0; i < a.size(); ++i) {
        if(a[i] == endpoint1) idx1 = i;
    }
    for(int i = 0; i < b.size(); ++i) {
        if(b[i] == endpoint2) idx2 = i;
    }

    vector<int> ans;
    for(int i = 0; i < a.size(); ++i) ans.push_back(a[(i + idx1 + 1) % a.size()]);
    for(int i = 0; i < b.size(); ++i) ans.push_back(b[(i + idx2) % b.size()]);
    return ans;
}