#include "longesttrip.h"
#include <bits/stdc++.h>

int search(std::vector<int> a, std::vector<int> b) {
    if (a.size() == 1) {
        return a[0];
    }
    int n1 = a.size() / 2;
    auto a0 = std::vector(a.begin(), a.begin() + n1);
    auto a1 = std::vector(a.begin() + n1, a.end());
    if (are_connected(a0, b)) {
        return search(a0, b);
    }
    return search(a1, b);
}

std::vector<int> longest_trip(int N, int D) {
    std::vector<int> a{0}, b{1};
    for (int i = 2; i < N; i++) {
        if (are_connected({a.back()}, {i})) {
            a.push_back(i);
        } else if (are_connected({b.back()}, {i})) {
            b.push_back(i);
        } else {
            a.insert(a.end(), b.rbegin(), b.rend());
            b = {i};
        }
    }
    
    if (are_connected({a[0]}, {b[0]})) {
        a.insert(a.begin(), b.rbegin(), b.rend());
        return a;
    }
    if (are_connected({a.back()}, {b[0]})) {
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }
    if (are_connected({a[0]}, {b.back()})) {
        b.insert(b.end(), a.begin(), a.end());
        return b;
    }
    if (!are_connected(a, b)) {
        return a.size() > b.size() ? a : b;
    }
    int x = search(a, b);
    int y = search(b, {x});
    std::rotate(a.begin(), std::find(a.begin(), a.end(), x) + 1, a.end());
    std::rotate(b.begin(), std::find(b.begin(), b.end(), y), b.end());
    a.insert(a.end(), b.begin(), b.end());
    return a;
}