#include "park.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e17;
const int mod2 = 1e9+7;
//const int base=67;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
int kk;
int el = 19;/*
main()
{
///top1tst
if(fopen(task2".inp","r"))
{
fin(task2);
fou(task2);
}
///top1tst
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
///top1tst
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
// cin>>s1;
// int t;cin>>t;while(t--)
phongbeo(),down
checktime
///top1tst
}
#define NMAX 1400
#define DMAX 7
#define QMAX 45000
static int T,N,M,Asktotal,Answertotal;
static int edge_list[NMAX][DMAX];
static int checked[NMAX][DMAX];
static int degree[NMAX];
static int visited[NMAX];
static void WA(int wa_num)
{
printf("Wrong Answer[%d]\n",wa_num);
exit(0);
}
void Detect(int T, int N);
void Answer(int A, int B)
{
int i;
if(A < 0||A >= B||B >= N) WA(1);
for(i = 0 ; i < degree[A] ; i++)
{
if(edge_list[A][i] == B)
{
if(checked[A][i] == 1) WA(3);
Answertotal++;
checked[A][i] = 1;
return;
}
}
WA(2);
}
static void dfs(int now, int Place[])
{
visited[now] = 1;
int i;
for(i = 0 ; i < degree[now] ; i++)
{
if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
}
}
int Ask(int A, int B, int Place[])
{
int i;
Asktotal++;
if(Asktotal>QMAX) WA(5);
if(A < 0||A >= B||B >= N) WA(4);
if(Place[A] != 1) WA(4);
if(Place[B] != 1) WA(4);
for(i = 0 ; i < N ; i++)
{
if(Place[i]<0||Place[i]>1) WA(4);
visited[i] = 0;
}
dfs(A, Place);
return visited[B];
}*/
vector<int> v[1401],ask;
int vis[1401];
bool f[1401];
int tak[1401];
void dfs(int x,int y,int cc)
{
vis[x]=1;
for(auto f:v[x])
dfs(f,y,cc);
if(vis[x]==1&&x!=y&&x!=cc)
ask.pb(x);
vis[x]=2;
}
void build(int x,int y)
{
ask.clear();
for(int i=0; i<n; i++)
vis[i]=0;
dfs(0,x,y);
for(int i=0; i<n; i++)
if(!vis[i]&&i!=x&&i!=y)ask.pb(i);
}
bool are_connect(int x,int y)
{
for(int i=0;i<n;i++)
if(i==x||i==y)tak[i]=1;
else tak[i]=0;
return Ask(min(x,y),max(y,x),tak);
}
void add(int x,int y)
{
if(f[y])return;
if(are_connect(x,y))
{
f[y]=1;
v[x].pb(y);
return;
}
build(x,y);
while(ask.size()>1)
{
vector<int> lft,rgt;
int mid=ask.size()/2;
for(int i=0; i<mid; i++)
lft.pb(ask[i]);
for(int i=mid;i<ask.size();i++)
rgt.pb(ask[i]);
for(int i=0;i<n;i++)
tak[i]=1;
for(auto g:lft)tak[g]=0;
if(Ask(min(x,y),max(x,y),tak))ask=rgt;
else ask=lft;
}
int mid=ask[0];
add(x,mid);
add(mid,y);
}
void Detect(int T,int N)
{
n=N;
for(int i=1; i<n; i++)
add(0,i);
for(int i=0; i<n; i++)
for(auto x:v[i])
Answer(min(x,i),max(x,i));
}/*
void phongbeo()
{
int i;
scanf("%d%d%d",&T,&N,&M);
Answertotal = 0;
for(i = 0 ; i < N ; i++) degree[i] = 0;
for(i = 0 ; i < M ; i++)
{
int ea,eb;
//scanf("%d%d",&ea,&eb);
ea=i;
eb=i+1;
checked[ea][degree[ea]] = 0;
checked[eb][degree[eb]] = 0;
edge_list[ea][degree[ea]++] = eb;
edge_list[eb][degree[eb]++] = ea;
}
Detect(T, N);
if(Answertotal<M) WA(6);
printf("Accepted\n");
}*/
