#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector <int> A, B;
bool know = 0;
A.push_back(0);
B.push_back(1);
for (int i=2;i<N;i++) {
if (are_connected({i},{B.back()})) {
B.push_back(i);
if (B.size() == 2) {
swap(B[0],B[1]);
}
else {
know = 0;
}
}
else if (know) {
A.push_back(i);
know = 0;
}
else if (are_connected({A.back()},{B.back()})) {
while (!B.empty()) {
A.push_back(B.back());
B.pop_back();
}
B.push_back(i);
}
else {
A.push_back(i);
know = 1;
}
}
if (!are_connected(A,B)) {
if (A.size() > B.size()) {
return A;
}
else {
return B;
}
}
vector <int> X, Y;
X.push_back(A.back());
Y.push_back(B.back());
if (A.size() > 1) {
X.push_back(A[0]);
}
if (B.size() > 1) {
Y.push_back(B[0]);
}
if (are_connected(X,Y)) {
if (are_connected({A.back()},{B.back()})) {
while (!B.empty()) {
A.push_back(B.back());
B.pop_back();
}
return A;
}
if (are_connected({A.back()},{B[0]})) {
for (int x : B) {
A.push_back(x);
}
return A;
}
if (are_connected({A[0]},{B.back()})) {
for (int x : A) {
B.push_back(x);
}
return B;
}
reverse(A.begin(),A.end());
for (int x : B) {
A.push_back(x);
}
return A;
}
int L=0, R=A.size()-1;
while (L < R) {
int mid = (L+R)/2;
vector <int> C;
for (int i=L;i<=mid;i++) {
C.push_back(A[i]);
}
if (are_connected(B,C)) {
R = mid;
}
else {
L = mid+1;
}
}
vector <int> C;
for (int i=L+1;i<A.size();i++) {
C.push_back(A[i]);
}
for (int i=0;i<=L;i++) {
C.push_back(A[i]);
}
L=0, R=B.size()-1;
while (L < R) {
int mid = (L+R)/2;
vector <int> D;
for (int i=L;i<=mid;i++) {
D.push_back(B[i]);
}
if (are_connected({C.back()},D)) {
R = mid;
}
else {
L = mid+1;
}
}
for (int i=L;i<B.size();i++) {
C.push_back(B[i]);
}
for (int i=0;i<L;i++) {
C.push_back(B[i]);
}
return C;
}
