#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int dc_left(vector<int> a, vector<int> b) {
if (a.size() == 1)
return a.back();
vector<int> left(a.begin(), a.begin() + a.size() / 2);
vector<int> right(a.begin() + a.size() / 2, a.end());
if (are_connected(left, b))
return dc_left(left, b);
else
return dc_left(right, b);
}
int dc_right(vector<int> a, vector<int> b) {
if (b.size() == 1)
return b.back();
vector<int> left(b.begin(), b.begin() + b.size() / 2);
vector<int> right(b.begin() + b.size() / 2, b.end());
if (are_connected(a, left))
return dc_right(a, left);
else
return dc_right(a, right);
}
vector<int> longest_trip(int N, int D) {
vector<deque<int>> comp(N);
for (int i = 0; i < N; i++)
comp[i].push_back(i);
set<pair<int, int>> known;
while (comp.size() > 2) {
int i = 0;
int j = 1;
int k = 2;
int u = comp[i].back();
int v = comp[j].back();
int w = comp[k].back();
int vv = comp[j].front();
int ww = comp[k].front();
if (!known.count(minmax(u, v)) && are_connected({u}, {v})) {
; // (u, v)
} else if (!known.count(minmax(vv, ww)) && are_connected({vv}, {ww})) {
; // (vv, ww)
known.insert(minmax(u, v));
reverse(comp[j].begin(), comp[j].end());
reverse(comp[k].begin(), comp[k].end());
swap(i, j);
swap(j, k);
} else if (!known.count(minmax(u, w)) && are_connected({u}, {w})) {
known.insert(minmax(u, v));
known.insert(minmax(vv, ww));
swap(j, k);
} else {
known.insert(minmax(u, v));
known.insert(minmax(vv, ww));
known.insert(minmax(u, w));
swap(i, j);
swap(j, k);
}
reverse(comp[j].begin(), comp[j].end());
comp[i].insert(comp[i].end(), comp[j].begin(), comp[j].end());
comp.erase(comp.begin() + j);
}
if (comp[0].size() < comp[1].size()) {
swap(comp[0], comp[1]);
}
if (are_connected({comp[0].back()}, {comp[1].back()})) {
reverse(comp[1].begin(), comp[1].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].back()}, {comp[1].front()})) {
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].front()}, {comp[1].front()})) {
reverse(comp[0].begin(), comp[0].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected({comp[0].front()}, {comp[1].back()})) {
reverse(comp[0].begin(), comp[0].end());
reverse(comp[1].begin(), comp[1].end());
comp[0].insert(comp[0].end(), comp[1].begin(), comp[1].end());
} else if (are_connected(vector<int>(comp[0].begin(), comp[0].end()),
vector<int>(comp[1].begin(), comp[1].end()))) {
// two cycles, connected
int l = dc_left(vector<int>(comp[0].begin(), comp[0].end()),
vector<int>(comp[1].begin(), comp[1].end()));
int r = dc_right({l}, vector<int>(comp[1].begin(), comp[1].end()));
int l_idx = find(comp[0].begin(), comp[0].end(), l) - comp[0].begin();
int r_idx = find(comp[1].begin(), comp[1].end(), r) - comp[1].begin();
vector<int> ret;
for (int i = 0; i < comp[0].size(); i++)
ret.push_back(comp[0][(l_idx + 1 + i) % comp[0].size()]);
for (int i = 0; i < comp[1].size(); i++)
ret.push_back(comp[1][(r_idx + i) % comp[1].size()]);
return ret;
}
return vector<int>(comp[0].begin(), comp[0].end());
}
