// #include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#include "longesttrip.h"
// #include <cassert>
// #include <cstdio>
// #include <string>
// #include <vector>
// int curr=0;
// static inline constexpr int maxNumberOfCalls = 32640;
// static inline constexpr int maxTotalNumberOfCalls = 150000;
// static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
// static int call_counter = 0;
// static int total_call_counter = 0;
// static int landmark_counter = 0;
// static int C, N, D;
// static std::vector<std::vector<int>> U;
// static std::vector<bool> present;
int c[257][257];
// static inline void protocol_violation(std::string message)
// {
// printf("Protocol Violation: %s\n", message.c_str());
// exit(0);
// }
// bool are_connected(std::vector<int> A, std::vector<int> B)
// {
// ++call_counter;
// ++total_call_counter;
// if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
// {
// protocol_violation("too many calls");
// }
// int nA = A.size(), nB = B.size();
// landmark_counter += nA + nB;
// if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
// {
// protocol_violation("too many elements");
// }
// if (nA == 0 || nB == 0)
// {
// protocol_violation("invalid array");
// }
// for (int i = 0; i < nA; ++i)
// {
// if (A[i] < 0 || N <= A[i])
// {
// protocol_violation("invalid array");
// }
// if (present[A[i]])
// {
// protocol_violation("invalid array");
// }
// present[A[i]] = true;
// }
// for (int i = 0; i < nA; ++i)
// {
// present[A[i]] = false;
// }
// for (int i = 0; i < nB; ++i)
// {
// if (B[i] < 0 || N <= B[i])
// {
// protocol_violation("invalid array");
// }
// if (present[B[i]])
// {
// protocol_violation("invalid array");
// }
// present[B[i]] = true;
// }
// for (int i = 0; i < nB; ++i)
// {
// present[B[i]] = false;
// }
// for (int i = 0; i < nA; ++i)
// {
// for (int j = 0; j < nB; ++j)
// {
// if (A[i] == B[j])
// {
// protocol_violation("non-disjoint arrays");
// }
// }
// }
// for (int i = 0; i < nA; ++i)
// {
// for (int j = 0; j < nB; ++j)
// {
// if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
// {
// return true;
// }
// }
// }
// return false;
// }
bool re_connected(int x,int y){
if(c[x][y]!=-1 )return c[x][y];
if(c[y][x]!=-1)return c[y][x];
if(x==y)return 0;
c[x][y]=are_connected({x},{y});
return c[x][y];
}
std::vector<int> longest_trip(int N, int D){
vector <int> v5;
curr=0;
// v5={0,13,1,3,9,2,7,12,14,8,11,15,5,4,6,10};
for(int i=0;i<N;i++){
v5.pb(i);
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
c[i][j]=-1;
}
}
shuffle(v5.begin(), v5.end(), mt19937());
vector <int> v1,v2;
v1.pb(v5[0]);
for(int i=1;i<N;i++){
if(re_connected(v1.back(),v5[i])){
v1.pb(v5[i]);
}else{
if(v2.empty() or (!re_connected(v2.back(),v1.back()))){
v2.pb(v5[i]);
}else{
reverse(v2.begin(),v2.end());
for(auto u:v2){
v1.pb(u);
}
v2.clear();
v2.pb(v5[i]);
}
}
}
// cout<<call_counter<<endl;
if(v1.size()!=1 and v2.size()!=1){
if(are_connected({v1[0],v1.back()},{v2[0],v2.back()})){
// cout<<"YES3"<<endl;
// for(int i=0;i<v5.size();i++){
// cout<<v5[i]<<" ";
// }
// cout<<endl;
// for(int i=0;i<v1.size();i++){
// cout<<v1[i]<<" ";
// }
// cout<<endl;
// for(int i=0;i<v2.size();i++){
// cout<<v2[i]<<" ";
// }
// cout<<endl;
if(are_connected({v1.back()},{v2[0]})){
for(auto u:v2){
v1.pb(u);
}
return v1;
}else if(are_connected({v1.back()},{v2.back()})){
reverse(v2.begin(),v2.end());
for(auto u:v2){
v1.pb(u);
}
return v1;
}else if(are_connected({v1[0]},{v2.back()})){
for(auto u:v1){
v2.pb(u);
}
return v2;
}else{
reverse(v2.begin(),v2.end());
for(auto u:v1){
v2.pb(u);
}
return v2;
}
}
}else{
if(v2.size()<=v1.size()){
swap(v1,v2);
}
if(are_connected({v1.back()},{v2[0],v2.back()})){
// cout<<"YES2"<<endl;
// for(int i=0;i<v5.size();i++){
// cout<<v5[i]<<" ";
// }
// cout<<endl;
if(are_connected({v1.back()},{v2[0]})){
for(auto u:v2){
v1.pb(u);
}
return v1;
}else{
v2.pb(v1[0]);
return v2;
}
}
// return {-1,-1,-1,-1};
}
// cout<<"YES1"<<endl;
// for(int i=0;i<v5.size();i++){
// cout<<v5[i]<<" ";
// }
// cout<<endl;
int l,r,ans,mid,ans1;
l=0;
r=v1.size()-1;
ans=-1;
while(l<=r){
mid=(l+r)/2;
vector <int> v3;
for(int i=0;i<=mid;i++){
v3.pb(v1[i]);
}
if(are_connected(v3,v2)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans==-1){
if(v1.size()>=v2.size()){
return v1;
}else{
return v2;
}
}
l=0;
r=v2.size()-1;
ans1=-1;
while(l<=r){
mid=(l+r)/2;
vector <int> v3;
for(int i=0;i<=mid;i++){
v3.pb(v2[i]);
}
if(are_connected({v1[ans]},v3)){
ans1=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans1<0){
assert(0);
}
vector <int> v;
for(int i=ans+1;i<v1.size();i++){
v.pb(v1[i]);
}
for(int i=0;i<=ans;i++){
v.pb(v1[i]);
}
for(int i=ans1;i<v2.size();i++){
v.pb(v2[i]);
}
for(int i=0;i<ans1;i++){
v.pb(v2[i]);
}
return v;
}
// int main()
// {
// assert(1 == scanf("%d", &C));
// int maximumCalls = 0;
// for (int c = 0; c < C; ++c)
// {
// call_counter = 0;
// assert(2 == scanf("%d %d", &N, &D));
// present.assign(N, false);
// U.resize(N);
// for (int i = 1; i < N; ++i)
// {
// U[i].resize(i);
// for (int j = 0; j < i; ++j)
// {
// assert(1 == scanf("%d", &U[i][j]));
// }
// }
// for (int i = 2; i < N; ++i)
// {
// for (int j = 1; j < i; ++j)
// {
// for (int k = 0; k < j; ++k)
// {
// if (U[i][j] + U[i][k] + U[j][k] < D)
// {
// printf("Insufficient Density\n");
// exit(0);
// }
// }
// }
// }
// std::vector<int> t = longest_trip(N, D);
// int l = t.size();
// printf("%d\n", l);
// for (int i = 0; i < l; ++i)
// {
// printf(i == 0 ? "%d" : " %d", t[i]);
// }
// printf("\n");
// cout<<curr<<endl;
// printf("%d\n", call_counter);
// maximumCalls = std::max(maximumCalls, call_counter);
// call_counter = 0;
// }
// printf("%d\n", maximumCalls);
// return 0;
// }
