#include<bits/stdc++.h>
#include "chameleon.h"
using namespace std ;
namespace {
vector < int > v[ 1007 ] ;
int col[ 1007 ] ;
vector < int > w[ 3 ] ;
vector < int > aux ;
bool done[ 1007 ] ;
int nxt[ 1007 ] , prv[ 1007 ] ;
}
void dfs ( int vertex , int c ) {
col[ vertex ] = c ;
for ( auto y : v[ vertex ] ) {
if ( col[ y ] == 0 ) {
dfs ( y , 3 - c ) ;
}
}
}
bool f ( int wh , int l , int r , int ori ) {
if ( l > r ) { return false ; }
aux.clear ( ) ;
aux.emplace_back ( ori ) ;
for ( int i = l ; i <= r ; ++ i ) {
aux.emplace_back ( w[ wh ][ i ] ) ;
}
int ret = Query ( aux ) ;
if ( ret <= r - l + 1 ) { return true ; }
return false ;
}
void Solve ( int n ) {
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
for ( int j = 1 ; j < i ; ++ j ) {
col[ j ] = 0 ;
}
for ( int j = 1 ; j < i ; ++ j ) {
if ( col[ j ] == 0 ) {
dfs ( j , 1 ) ;
}
}
w[ 1 ].clear ( ) ; w[ 2 ].clear ( ) ;
for ( int j = 1 ; j < i ; ++ j ) {
w[ col[ j ] ].push_back ( j ) ;
}
for ( int wh = 1 ; wh <= 2 ; ++ wh ) {
int lst = -1 ;
for ( int tm = 0 ; tm < 3 ; ++ tm ) {
int l , r , mid ;
l = lst + 1 ;
r = w[ wh ].size ( ) - 1 ;
if ( f ( wh , lst + 1 , r , i ) == false ) { break ; }
while ( r - l > 3 ) {
mid = ( l + r ) / 2 ;
if ( f ( wh , lst + 1 , mid , i ) == true ) { r = mid ; }
else { l = mid ; }
}
while ( f ( wh , lst + 1 , l , i ) == false ) { ++ l ; }
v[ i ].push_back ( w[ wh ][ l ] ) ;
v[ w[ wh ][ l ] ].push_back ( i ) ;
lst = l ;
}
}
}
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
if ( v[ i ].size ( ) == 1 && done[ i ] == false ) {
Answer ( i , v[ i ][ 0 ] ) ;
done[ i ] = done[ v[ i ][ 0 ] ] = true ;
}
}
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
if ( v[ i ].size ( ) == 3 ) {
for ( int j = 0 ; j < 3 ; ++ j ) {
aux.clear ( ) ;
aux.push_back ( i ) ;
for ( int t = 0 ; t < 3 ; ++ t ) {
if ( j == t ) { continue ; }
aux.push_back ( v[ i ][ t ] ) ;
}
if ( Query ( aux ) == 1 ) {
nxt[ i ] = v[ i ][ j ] ;
prv[ v[ i ][ j ] ] = i ;
break ;
}
}
}
}
for ( int i = 1 ; i <= 2 * n ; ++ i ) {
if ( v[ i ].size ( ) == 3 && done[ i ] == false ) {
int sm = v[ i ][ 0 ] + v[ i ][ 1 ] + v[ i ][ 2 ] ;
sm = sm - prv[ i ] - nxt[ i ] ;
Answer ( i , sm ) ;
done[ i ] = done[ sm ] = true ;
}
}
}
