#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
int rand(int a, int b) {
return rand()%(b-a+1) + a;
}
int n;
vi pai;
vector<vi> comp;
int find(int x) {
if(x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
int join(int x, int y) {
if(x == -1) return y;
x = find(x);
y = find(y);
if(x == y) return x;
if(sz(comp[x]) > sz(comp[y])) swap(x,y);
pai[x] = y;
for(auto it : comp[x]) comp[y].pb(it);
comp[x].clear();
return y;
}
int find_edge(int X, vi &out) {
int click = -1, C = -1;
random_shuffle(all(out));
for(auto A : out) {
if(are_connected({X}, comp[A])) {
C = A;
break;
}
else click = join(click, A);
}
for(int i = 0; i < sz(out); i++) {
if(pai[out[i]] != out[i] or out[i] == C)
out.erase(out.begin() + i), i--;
}
if(C == -1) return -1;
int l = 0, r = sz(comp[C]) - 1;
while(l < r) {
int mid = (l+r)/2;
vi aux;
for(int i = l; i <= mid; i++)
aux.pb(comp[C][i]);
if(are_connected({X}, aux)) r = mid;
else l = mid+1;
}
l = comp[C][l];
pai[C] = l;
swap(comp[l], comp[C]);
pai[l] = l;
return l;
}
vi longest_trip(int N, int D) {
srand(93652);
n = N;
pai.clear();
pai.resize(N);
comp.clear();
comp.resize(N);
vi cam = {rand(0, N-1)};
vi out;
for(int i = 0; i < N; i++) {
pai[i] = i;
comp[i].pb(i);
if(i != cam[0]) out.pb(i); // randomizar
}
while(sz(cam) < N) {
int A = find_edge(cam.back(), out);
if(A != -1) {
cam.pb(A);
for(auto it : comp[A])
if(it != A) cam.pb(it);
continue;
}
vi out_cam;
for(auto C : out) {
for(auto it : comp[C])
out_cam.pb(it);
}
if(!are_connected(cam, out_cam)) {
if(sz(cam) >= sz(out_cam)) return cam;
return out_cam;
}
int l = 0, r = sz(cam) - 2;
while(l < r) {
int mid = (l+r)/2;
vi aux;
for(int i = l; i <= mid; i++)
aux.pb(cam[i]);
if(are_connected(aux, out_cam)) r = mid;
else l = mid+1;
}
l = cam[l];
while(cam[0] != l) {
cam.pb(cam[0]);
cam.erase(cam.begin());
}
reverse(all(cam));
}
return cam;
}
