#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
static inline void rotate_to(vector<int>& p, int idx) {
// rotate so that p[idx] becomes first
rotate(p.begin(), p.begin() + idx, p.end());
}
vector<int> longest_trip(int N, int D) {
// Optional fast path for D=3 clique: no queries needed.
// (Not required, but nice.)
if (D == 3) {
vector<int> t(N);
iota(t.begin(), t.end(), 0);
return t;
}
vector<int> p1, p2;
p1.push_back(N - 1);
// handle N even: place N-2 either next to N-1 or start p2
if (N % 2 == 0) {
if (are_connected({N - 2}, {N - 1})) p1.push_back(N - 2);
else p2.push_back(N - 2);
}
// process vertices in pairs: (0,1), (2,3), ...
for (int i = 0; i < N - 2; i += 2) {
int v = i, w = i + 1;
if (p2.empty()) {
// only p1 exists
bool vw = are_connected({v}, {w});
bool tv = are_connected({p1.back()}, {v});
bool tw = are_connected({p1.back()}, {w});
if (vw) {
if (tv) { p1.push_back(v); p1.push_back(w); }
else if (tw) { p1.push_back(w); p1.push_back(v); }
else { p2.push_back(v); p2.push_back(w); } // start second path
} else {
// need split them between p1 and p2 or append one to p1
if (tv) { p1.push_back(v); p2.push_back(w); }
else { p2.push_back(v); p1.push_back(w); }
}
} else {
// both paths exist
bool vw = are_connected({v}, {w});
if (vw) {
if (!are_connected({p1.back()}, {v})) swap(p1, p2);
if (are_connected({p2.back()}, {w})) {
// merge into one path
p1.push_back(v);
p1.push_back(w);
for (int k = (int)p2.size() - 1; k >= 0; k--) p1.push_back(p2[k]);
p2.clear();
} else {
p1.push_back(v);
p1.push_back(w);
}
} else {
if (!are_connected({p1.back()}, {v})) swap(p1, p2);
if (are_connected({p2.back()}, {w})) {
p1.push_back(v);
p2.push_back(w);
} else {
p1.push_back(w);
p2.push_back(v);
}
}
}
}
if ((int)p1.size() < (int)p2.size()) swap(p1, p2);
if (p2.empty()) return p1;
// If no edge between sets => different components => longest path is in larger component.
if (!are_connected(p1, p2)) return p1;
auto has_cycle_edge = [&](const vector<int>& p) -> bool {
if ((int)p.size() <= 2) return true;
return are_connected({p.front()}, {p.back()});
};
// If both can be closed into cycles, but no endpoint-endpoint edges,
// we find a cross-edge by binary searching.
if (has_cycle_edge(p1) && has_cycle_edge(p2)) {
int s2 = 0, e2 = (int)p2.size();
while (e2 - s2 > 1) {
int m2 = (s2 + e2) / 2;
vector<int> q(p2.begin() + s2, p2.begin() + m2);
if (are_connected(p1, q)) e2 = m2;
else s2 = m2;
}
int k2 = s2; // p2[k2] has an edge to p1
int s1 = 0, e1 = (int)p1.size();
while (e1 - s1 > 1) {
int m1 = (s1 + e1) / 2;
vector<int> q(p1.begin() + s1, p1.begin() + m1);
if (are_connected(q, {p2[k2]})) e1 = m1;
else s1 = m1;
}
int k1 = s1; // p1[k1] connects to p2[k2]
rotate_to(p1, k1);
rotate_to(p2, k2);
reverse(p2.begin(), p2.end());
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
// Otherwise, try to connect via endpoints (at least one must work here).
if (are_connected({p1.front()}, {p2.front()})) {
reverse(p2.begin(), p2.end());
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
if (are_connected({p1.front()}, {p2.back()})) {
p2.insert(p2.end(), p1.begin(), p1.end());
return p2;
}
if (are_connected({p1.back()}, {p2.front()})) {
p1.insert(p1.end(), p2.begin(), p2.end());
return p1;
}
if (are_connected({p1.back()}, {p2.back()})) {
reverse(p2.begin(), p2.end());
p1.insert(p1.end(), p2.begin(), p2.end());
return p1;
}
// In theory unreachable if density constraints hold
return p1;
}
