#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool adj(int x, int y){
return are_connected(vector<int>(1, x), vector<int>(1, y));
}
void mergeVec(vector<int> &A, vector<int> &B){
while(!B.empty()) A.push_back(B.back()), B.pop_back();
}
vector<int> sliceVec(vector<int> A, int idx){
vector<int> ret = A;
while((int)ret.size()-1 > idx) ret.pop_back();
return ret;
}
vector<int> longest_trip(int N, int D){
if(D == 3){
vector<int> v;
for(int i=0; i<N; i++){
v.push_back(i);
}
return v;
}
if(D == 2){
list<int> v;
v.push_back(0);
if(are_connected(vector<int> (1, 0), vector<int> (1, 1))){
v.push_back(1);
if(are_connected(vector<int> (1, 1), vector<int> (1, 2))) v.push_back(2);
else v.push_front(2);
}
else{
v.push_back(2);
v.push_back(1);
}
for(int i=3; i<N; i++){
if(are_connected(vector<int> (1, v.front()), vector<int> (1, i))) v.push_front(i);
else v.push_back(i);
}
vector<int> vec;
while(!v.empty()) vec.push_back(v.front()), v.pop_front();
return vec;
}
vector<int> pathA, pathB;
if(adj(0, 1)) pathA.push_back(0), pathA.push_back(1);
else pathA.push_back(0), pathB.push_back(1);
for(int v=2; v<N; v+=2){
if(v == N-1){ /// 하나 남은 경우
bool a = adj(v, pathA.back()), b = pathB.empty() ? 0 : adj(v, pathB.back());
if(a && b){
pathA.push_back(v);
mergeVec(pathA, pathB);
}
else if(a) pathA.push_back(v);
else if(b) pathB.push_back(v);
break;
}
int w = v+1;
if(pathB.empty()){ /// 경로가 하나
int a = pathA.back();
bool av = adj(a, v), aw = adj(a, w), vw = adj(v, w);
if(vw && av) pathA.push_back(v), pathA.push_back(w);
else if(vw && aw) pathA.push_back(w), pathA.push_back(v);
else if(vw) pathB.push_back(v), pathB.push_back(w);
else if(av) pathA.push_back(v), pathB.push_back(w);
else pathA.push_back(w), pathB.push_back(v);
}
else{
int a = pathA.back(), b = pathB.back();
if(adj(v, w)){
if(adj(a, v)){
pathA.push_back(v), pathA.push_back(w);
if(adj(b, w)) mergeVec(pathA, pathB);
}
else{ /// b, v가 인접
pathB.push_back(v), pathB.push_back(w);
if(adj(a, w)) mergeVec(pathA, pathB);
}
}
else{
if(adj(a, v) && adj(b, w)) pathA.push_back(v), pathB.push_back(w);
else pathA.push_back(w), pathB.push_back(v);
}
}
}
/// 두 path로 축약까지 성공, 여기까지 382
if(pathA.size() < pathB.size()) swap(pathA, pathB);
/// 잇는 간선이 없다면...
if(pathB.empty() || !are_connected(pathA, pathB)) return pathA;
/// 양끝점 연결 여부 확인
{
vector<int> vA = {pathA[0], pathA.back()};
if((int)pathA.size() == 1) vA.pop_back();
vector<int> vB = {pathB[0], pathB.back()};
if((int)pathB.size() == 1) vB.pop_back();
if(are_connected(vA, vB)){ /// 양끝점 중 연결된 쌍이 있다
int af = pathA[0], ab = pathA.back(), bf = pathB[0], bb = pathB.back();
if(adj(af, bf)) reverse(pathA.begin(), pathA.end()), reverse(pathB.begin(), pathB.end());
else if(adj(af, bb)) reverse(pathA.begin(), pathA.end());
else if(adj(ab, bf)) reverse(pathB.begin(), pathB.end());
mergeVec(pathA, pathB);
return pathA;
}
}
/// 나머지를 사이클로 볼 수 있다.
int L = 0, R = (int)pathA.size() - 1;
while(L<R){
int M = (L+R)/2;
if(are_connected(sliceVec(pathA, M), pathB)) R=M;
else L=M+1;
}
rotate(pathA.begin(), pathA.begin() + L, pathA.end());
reverse(pathA.begin(), pathA.end());
L = 0, R = (int)pathB.size() - 1;
while(L<R){
int M = (L+R)/2;
if(are_connected(vector<int> (1, pathA.back()), sliceVec(pathB, M))) R=M;
else L=M+1;
}
rotate(pathB.begin(), pathB.begin() + L, pathB.end());
reverse(pathB.begin(), pathB.end());
mergeVec(pathA, pathB);
return pathA;
}
