#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;
vector<int> s;
vector<int> used;
int n;
int endik = -1;
/*
bool are_connected(vector<int> a, vector<int> b) {
cout <<endl << "QUERY" << endl;
for (auto el : a) {
cout << el << " ";
}
cout << endl << "and" << endl;
for (auto el : b) {
cout << el << " ";
}
cout << endl;
int x;
cin >> x;
return (x == 1);
}
*/
vector<int> longest_trip(int N, int d) {
n = N;
vector<int> p, q;
p.push_back(0);
for (int i = 1; i < n; i++) {
if (are_connected({0}, {i})) {
p.push_back(i);
} else {
q.push_back(i);
}
}
if (are_connected(p, q)) {
int m = q.size();
int l = -1, r = m-1;
vector<int> pa;
while (r - l > 1) {
int mid = (l + r) / 2;
pa.clear();
for (int i = 0; i <= mid; i++) {
pa.push_back(q[i]);
}
if (are_connected(p, pa)) {
r = mid;
} else {
l = mid;
}
}
int conq = q[r];
m = p.size();
l = -1;
r = m - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
pa.clear();
for (int i = 0; i <= mid; i++) {
pa.push_back(p[i]);
}
if (are_connected(pa, {conq})) {
r = mid;
} else {
l = mid;
}
}
int conp = p[r];
vector<int> res;
for (auto el : q) {
if (el != conq) {
res.push_back(el);
}
}
res.push_back(conq);
res.push_back(conp);
for (auto el : p) {
if (el != conp) {
res.push_back(el);
}
}
return res;
} else {
if (p.size() < q.size()) {
swap(p, q);
}
return p;
}
}
/*
signed main() {
int N, D;
cin >> N >> D;
auto res = longest_trip(N, D);
for (auto el : res) {
cout << el << ' ';
}
cout << endl;
}
*/
