#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
bool check( int x, int y ){
vi a = {x}, b = {y};
return are_connected( a, b );
}
bool query( vi &a, vi &b, int la, int ra ){
vi aux( a.begin() + la, a.begin() + ra );
return are_connected( aux, b );
}
void merge( vi &a, vi &b ){
while( !b.empty() ){
a.push_back(b.back());
b.pop_back();
}
}
vi solve3( int n ){
vi v(n);
iota( v.begin(), v.end(), 0 );
return v;
}
vi solve2( int n ){
vi a( 1, 0 ), b( 1, 1 );
for( int i = 2; i < n; i++ ){
if( check( a.back(), i ) ){ a.push_back(i); continue; }
if( check( b.back(), i ) ){ b.push_back(i); continue; }
merge( a, b );
b.push_back(i);
}
if( !query( a, b, 0, a.size() ) ) return a;
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( a.begin(), a.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( b.begin(), b.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( a.begin(), a.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
return a;
}
int bs( vector<int> &a, vector<int> &b ){
int l = 0, r = a.size();
while( l + 1 < r ){
int mid = ( l + r )/2;
if( !query( a, b, l, mid ) ) l = mid;
else r = mid;
}
return l;
}
vi solve1( int n ){
vi a( 1, 0 ), b( 1, 1 );
for( int i = 2; i < n; i++ ){
if( check( a.back(), i ) ){ a.push_back(i); continue; }
if( check( b.back(), i ) ){ b.push_back(i); continue; }
merge( a, b );
b.push_back(i);
}
if( !query( a, b, 0, a.size() ) ) return a;
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( a.begin(), a.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( b.begin(), b.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
reverse( a.begin(), a.end() );
if( check( a.back(), b.back() ) ){
merge( a, b );
return a;
}
int id1 = bs( a, b );
int id2 = bs( b, a );
vi resp;
for( int i = (id1 + 1)%a.size(); resp.size() < a.size(); i = (i + 1)%a.size() )
resp.push_back(a[i]);
for( int i = id2; (int)resp.size() < n; i = (i + 1)%b.size() )
resp.push_back(b[i]);
return resp;
}
vi longest_trip( int n, int d ){
if( d == 3 ) return solve3(n);
if( d == 2 ) return solve2(n);
return solve1(n);
}
