//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
// swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std ;
vector<int> r ;
void solve(int N, int V)
{
vector< vector<int> > space ;
for(int i = 1 ; i <= N ; i++ ) space.push_back({i}) ;
while( sz(space) > 1 )
{
/*for(auto e : space )
{
for(auto ee : e ) cout <<ee <<" " ;
cout << endl ;
}*/
vector< vector<int> > aux ;
sort(all(space), [&](vector<int> a, vector<int> b) { return sz(a) > sz(b) ; }) ;
int p = sz(space[0]) ;
for(int i = 0 ; i+1 < sz(space) ; i += 2 )
aux.push_back(vector<int>(sz(space[i])+sz(space[i+1]) , 0)) ;
if( sz(space)&1 ) aux.push_back( space.back() ) ;
while(p--)
{
for(int i = 0 ; i+1 < sz(space) ; i += 2 )
for(int j = 0 ; j < sz(space[i+1]) ; j++ )
schedule( space[i][j] , space[i+1][j] ) ;
r = visit() ;
int id = 0 ;
for(int i = 0 ; i+1 < sz(space) ; i += 2 )
{
for(int j = 0 ; j < sz(space[i+1]) ; j++ )
if(!r[id++]) swap( space[i][j] , space[i+1][j] ) ;
int t1 = sz(space[i]) , t2 = sz(space[i+1]) ;
for(int j = 0 ; j < sz(aux[i>>1]) ; j++ )
if( aux[i>>1][j] == 0 )
{
aux[i>>1][j] = space[i][0] ;
break ;
}
space[i].erase( space[i].begin() , space[i].begin()+1 ) ;
if(t1 == t2)
{
for(int j = sz(aux[i>>1])-1 ; j >= 0 ; j-- )
if(aux[i>>1][j] == 0)
{
aux[i>>1][j] = space[i+1].back() ;
break ;
}
space[i+1].erase( space[i+1].begin()+t2-1 , space[i+1].end() ) ;
}
}
}
swap(aux, space) ;
}
answer(space[0]) ;
}
