#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> longest_trip(int N, int D) {
if (D >= 2) {
set<int> s;
for (int i = 1; i < N; ++i) {
s.insert(i);
}
vector<int> ans = {0};
while (!s.empty()) {
int v = ans.back();
bool found = 0;
for (int to : s) {
bool b = are_connected({v}, {to});
if (b) {
s.erase(to);
ans.push_back(to);
found = 1;
break;
}
}
if (!found) {
int last = *s.begin();
ans.insert(ans.begin(), last);
break;
}
}
return ans;
}
// if (N == 3) {
// int cnt = 0;
// int x = 0;
// auto go = [&](int i, int j) {
// if (are_connected({i}, {j})) {
// cnt++;
// x ^= i;
// x ^= j;
// }
// };
// go(0, 1);
// go(0, 2);
// go(1, 2);
// if (cnt == 0) return {0};
// int other = 3^x;
// set<int> s = {0, 1, 2};
// s.erase(other);
// int v1 = *s.begin();
// int v2 = *(++s.begin());
// if (cnt == 1) {
// return {v1, v2};
// }
// return {v1, other, v2};
// }
// check if single component
// if not, each component is clique, problem is then find largest component
// otherwise, one component,
// start with one node and keep trying to extend path by randomly querying
// if gets stuck, that means past must be a clique, done
int calls = 0;
auto my_are_connected = [&](vector<int> a, vector<int> b) {
calls ++;
assert(calls <= 32460);
return are_connected(a, b);
};
bool found = 0;
vector<int> answer;
using vi = vector<int>;
auto halves = [&](vector<int> v) -> pair<vi, vi> {
int m = v.size() / 2;
return {{v.begin(), v.begin()+m}, {v.begin()+m, v.end()}};
};
vector<int> path = {0};
vector<int> left(N-1);
iota(left.begin(), left.end(), 1);
while (left.size()) {
random_shuffle(left.begin(), left.end());
// cout << "! ";
// for (int x : left) {
// cout << x << " ";
// }
// cout << '\n';
auto locate = [&](vector<int> src, vector<int> dest) -> int {
while (src.size() != 1) {
auto [a, b] = halves(src);
if (my_are_connected(a, dest)) src = a;
else src = b;
}
return src[0];
};
int v = path.back();
int nxt = locate(left, {v});
if (!my_are_connected({nxt}, {v})) {
if (!my_are_connected(path, left)) {
if (path.size() > left.size()) return path;
else return left;
}
int a = locate(path, left);
int b = locate(left, {a});
vector<int> ans = left;
ans.erase(find(ans.begin(), ans.end(), b));
ans.push_back(b);
int j = find(path.begin(), path.end(), a) - path.begin();
if (j == 0) {
for (int x : path) {
ans.push_back(x);
}
}
else {
for (int i = j; i >= 0; --i) {
ans.push_back(path[i]);
}
for (int i = path.size()-1; i > j; --i) {
ans.push_back(path[i]);
}
}
for (int i = 1; i < ans.size(); ++i) {
assert(my_are_connected({ans[i]}, {ans[i-1]}));
}
return ans;
// path.erase(find(path.begin(), path.end(), a));
// left.erase(find(left.begin(), left.end(), b));
// path.push_back(a);
// left.insert(left.begin(), a);
// for (int x : left) path.push_back(x);
// return path;
// int lst = end(path)[-2];
// vector<int> ans = {v, lst};
// for (int i = 0; i < N; ++i) {
// if (i != v && i != lst) ans.push_back(i);
// }
// for (int i = 1; i < ans.size(); ++i) {
// assert(my_are_connected({ans[i]}, {ans[i-1]}));
// }
// return ans;
}
else {
path.push_back(nxt);
left.erase(find(left.begin(), left.end(), nxt));
}
}
for (int i = 1; i < path.size(); ++i) {
assert(my_are_connected({path[i]}, {path[i-1]}));
}
return path;
}
