#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
struct XorList {
struct Node {
int val;
Node *x, *y;
Node(int val) : val(val), x(NULL), y(NULL) { }
} *start, *end;
void merge(XorList *o) {
if (end->x == NULL) {
end->x = o->start;
} else {
end->y = o->start;
}
if (o->start->x == NULL) {
o->start->x = end;
} else {
o->start->y = end;
}
end = o->end;
o->start = o->end = NULL;
}
vector<int> vectorize() {
vector<int> ans;
Node* curr = start, *old = NULL;
while (curr != NULL) {
ans.push_back(curr->val);
if (old == curr->x) {
old = curr;
curr = old->y;
} else {
old = curr;
curr = old->x;
}
}
return ans;
}
int last() { return end->val; }
void reverse() { swap(start, end); }
XorList(int val) { start = end = new Node(val); }
};
vector<int> longest_trip(int N, int D) {
XorList *a = new XorList(0);
XorList *b = new XorList(1);
for (int i = 2; i < N; i++) {
int last_a = a->last();
int last_b = b->last();
XorList *m = new XorList(i);
if (are_connected({last_a}, {last_b})) {
b->reverse();
a->merge(b);
b = m;
} else if (are_connected({last_a}, {i})) {
a->merge(m);
} else {
b->merge(m);
}
}
vector<int> chain_a = a->vectorize();
vector<int> chain_b = b->vectorize();
if (chain_a.size() > chain_b.size()) {
return chain_a;
} else {
return chain_b;
}
}
