#include <iostream>
#include "longesttrip.h"
#include <vector>
using namespace std;
int adj[500][500];
int ls1[500];
int ls2[500];
int cnt1;
int cnt2;
int tem[500];
vector<int> vec1,vec2,vec3;
bool na1, na2;
int l1,r1,l2,r2;
int mi;
vector<int> longest_trip(int n, int d){
cnt1 = 0;
cnt2 = 0;
for(int i=0; i<n; i++){ls1[i] = 0; ls2[i] = 0;}
ls1[0] = 0;
ls2[0] = 1;
cnt1++;
cnt2++;
for(int i=2; i<n; i++){
vec1.clear();
vec2.clear();
vec3.clear();
vec1.push_back(i);
vec2.push_back(ls1[cnt1-1]);
vec3.push_back(ls2[cnt2-1]);
na1 = are_connected(vec1, vec2);
na2 = are_connected(vec1, vec3);
if(na1){
ls1[cnt1] = i;
cnt1++;
}
else if(na2){
ls2[cnt2] = i;
cnt2++;
}
else {
for(int j=0; j<cnt2; j++){
ls1[cnt1+cnt2-1-j] = ls2[j];
}
cnt1 += cnt2;
cnt2 = 1;
ls2[0] = i;
}
}
vec1.clear();
vec2.clear();
for(int i=0; i<cnt1; i++){
vec1.push_back(ls1[i]);
}
for(int i=0; i<cnt2; i++){
vec2.push_back(ls2[i]);
}
na1 = are_connected(vec1, vec2);
if(!na1){
vec3.clear();
if(cnt1>=cnt2){
for(int i=0; i<cnt1; i++){
vec3.push_back(ls1[i]);
}
}
else {
for(int i=0; i<cnt2; i++){
vec3.push_back(ls2[i]);
}
}
return vec3;
}
vec1.clear();
vec2.clear();
vec3.clear();
vec1.push_back(ls1[cnt1-1]);
vec2.push_back(ls2[cnt2-1]);
vec3.push_back(ls2[0]);
na1 = are_connected(vec1, vec2);
na2 = are_connected(vec1, vec3);
if(na1){
for(int j=0; j<cnt2; j++){
ls1[cnt1+cnt2-1-j] = ls2[j];
}
cnt1 += cnt2;
cnt2 = 0;
vec3.clear();
for(int i=0; i<cnt1; i++){
vec3.push_back(ls1[i]);
}
return vec3;
}
if(na2){
for(int j=0; j<cnt2; j++){
ls1[cnt1+j] = ls2[j];
}
cnt1 += cnt2;
cnt2 = 0;
vec3.clear();
for(int i=0; i<cnt1; i++){
vec3.push_back(ls1[i]);
}
return vec3;
}
for(int i=0; i<cnt1/2; i++){
swap(ls1[i], ls1[cnt1-1-i]);
}
vec1.clear();
vec2.clear();
vec3.clear();
vec1.push_back(ls1[cnt1-1]);
vec2.push_back(ls2[cnt2-1]);
vec3.push_back(ls2[0]);
na1 = are_connected(vec1, vec2);
na2 = are_connected(vec1, vec3);
if(na1){
for(int j=0; j<cnt2; j++){
ls1[cnt1+cnt2-1-j] = ls2[j];
}
cnt1 += cnt2;
cnt2 = 0;
vec3.clear();
for(int i=0; i<cnt1; i++){
vec3.push_back(ls1[i]);
}
return vec3;
}
if(na2){
for(int j=0; j<cnt2; j++){
ls1[cnt1+j] = ls2[j];
}
cnt1 += cnt2;
cnt2 = 0;
vec3.clear();
for(int i=0; i<cnt1; i++){
vec3.push_back(ls1[i]);
}
return vec3;
}
l1 = 0;
r1 = cnt1-1;
l2 = 0;
r2 = cnt2-1;
vec2.clear();
for(int i=0; i<cnt2; i++){
vec2.push_back(ls2[i]);
}
while(l1<r1){
mi = (l1+r1)/2;
vec1.clear();
for(int i=l1; i<=mi; i++){
vec1.push_back(ls1[i]);
}
na1 = are_connected(vec1, vec2);
if(na1){
r1 = mi;
}
else {
l1 = mi+1;
}
}
vec1.clear();
vec1.push_back(ls1[l1]);
while(l2<r2){
mi = (l2+r2)/2;
vec2.clear();
for(int i=l2; i<=mi; i++){
vec2.push_back(ls2[i]);
}
na1 = are_connected(vec1, vec2);
if(na1){
r2 = mi;
}
else {
l2 = mi+1;
}
}
vec3.clear();
for(int i=1; i<=cnt1; i++){
vec3.push_back(ls1[(l1+i)%cnt1]);
}
for(int i=0; i<cnt2; i++){
vec3.push_back(ls2[(l2+i)%cnt2]);
}
return vec3;
}
