#include "bits/stdc++.h"
#include "longesttrip.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=300;
int n, d;
map<pii, bool> mp;
bool con(int a, int b) {
if(mp.count({a,b})) return mp[{a,b}];
if(mp.count({b,a})) return mp[{b,a}];
return mp[{a,b}]=are_connected({a},{b});
}
void mrg(vi &a, vi &b) {
while(!b.empty()) {
a.pb(b.back());
b.pop_back();
}
}
void dbg(vi &a, vi&b) {
cout << "a: "; for(auto it : a) cout << it << " "; cout << endl;
cout << "b: "; for(auto it : b) cout << it << " "; cout << endl;
}
std::vector<int> longest_trip(int N, int D) {
mp.clear();
n=N; d=D;
vi in; FOR(i, 0, n) in.pb(i);
shuffle(in.begin(), in.end(), rng);
bool conn=true;
vi a, b; a.pb(in[0]);
FOR(i, 1, n) {
if(b.empty()) {
b.pb(in[i]);
continue;
}
if(con(a.back(), in[i])) a.pb(in[i]), conn=true;
else if(!conn) b.pb(in[i]);
else if(con(b.back(), in[i])) b.pb(in[i]), conn=false;
else mrg(a, b), b.pb(in[i]), conn=true;
}
if(b.empty()) return a;
if(con(a[0], b[0])) {
reverse(a.begin(), a.end());
for(auto it : b) a.pb(it);
return a;
}
if(con(a[0], b.back())) {
for(auto it : a) b.pb(it);
return b;
}
if(con(a.back(), b[0])) {
for(auto it : b) a.pb(it);
return a;
}
if(con(a.back(), b.back())) {
while(!b.empty()) a.pb(b.back()), b.pop_back();
return a;
}
if(sz(b)>sz(a)) swap(a, b);
if(!are_connected(a, b)) return a;
int l=0, r=sz(b)-1;
while(l<r) {
int m=(l+r)/2;
vi tmp; FOR(i, l, m+1) tmp.pb(b[i]);
if(are_connected(a, tmp)) r=m;
else l=m+1;
}
assert(are_connected({b[l]}, a));
int bin=l;
l=0; r=sz(a)-1;
while(l<r) {
int m=(l+r)/2;
vi tmp; FOR(i, l, m+1) tmp.pb(a[i]);
if(are_connected({b[bin]}, tmp)) r=m;
else l=m+1;
}
int ain=l;
// cout << ":\n";
// for(auto it : a) cout << it << " "; cout << endl;
// for(auto it : b) cout << it << " ";
// cout << "ins: " << ain << " " << bin << endl;
vi ans;
FOR(i, 1, sz(a)+1) {
int id=(ain+i)%sz(a);
ans.pb(a[id]);
}
FOR(i, 0, sz(b)) {
int id=(bin+i)%sz(b);
ans.pb(b[id]);
}
return ans;
}
/*
1
5 1
1
1 1
0 0 1
0 0 0 1
*/
