#include "park.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int query_arr[2002];
bool visited[2002];
int par[2002];
int depth[2002];
bool inRecursion[2002];
void query_select(vector<int>& v){
for(int i=0; i<n; i++) query_arr[i] = 0;
for(auto x: v) query_arr[x] = 1;
}
void solve(int x){
inRecursion[x] = 1;
/// 현재 방문한 곳만으로 접근 가능한지 판별
for(int i=0; i<n; i++){
query_arr[i] = visited[i];
}
query_arr[x] = 1;
if(Ask(0, x, query_arr)){ /// 접근 가능
vector<int> vec;
for(int i=0; i<n; i++) if(visited[i]) vec.push_back(i);
sort(vec.begin(), vec.end(), [&](int a, int b){
return depth[a] < depth[b];
});
int l = 0, r = (int)vec.size()-1;
while(l<r){
int m = (l+r)>>1;
memset(query_arr, 0, sizeof(query_arr));
vector<int> checklist;
for(int i=l; i<=m; i++){
checklist.push_back(vec[i]);
query_arr[vec[i]] = 1;
}
for(int i=0; i<(int)checklist.size(); i++){
if(checklist[i] && !query_arr[par[checklist[i]]]){
checklist.push_back(par[checklist[i]]);
query_arr[par[checklist[i]]] = 1;
}
}
query_arr[x] = 1;
bool ret = Ask(0, x, query_arr);
for(auto v: checklist) query_arr[v] = 0;
if(ret) r = m;
else l = m+1;
}
par[x] = vec[l];
Answer(min(par[x], x), max(par[x], x));
visited[x] = 1;
depth[x] = depth[par[x]] + 1;
}
else{
vector<int> vec;
for(int i=0; i<n; i++) if(!inRecursion[i] && x!=i) vec.push_back(i);
int l = 0, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
while(l<=r){
int m = (l+r)>>1;
for(int i=0; i<=m; i++){
query_arr[vec[i]] = 1;
}
bool ret = Ask(0, x, query_arr);
for(int i=0; i<=m; i++){
query_arr[vec[i]] = 0;
}
if(ret){ /// 접근 가능 -> 줄여야 함
qa = m;
r = m-1;
}
else{
l = m+1;
}
}
solve(vec[qa]);
solve(x);
}
}
int deg[2002];
vector<int> link[2002];
bool chk[2002][2002];
void dfs_insert(int x, int p, vector<int>& v){
if(deg[x] < 7) v.push_back(x);
for(auto y: link[x]){
if(p==y) continue;
dfs_insert(y, x, v);
}
}
void reorder(int x, int p = -1){
par[x] = p;
for(auto y: link[x]){
if(p==y) continue;
depth[y] = depth[x] + 1;
reorder(y, x);
}
}
void solve_cross(int o, int x, int p){ /// o - ... - p - x
if(deg[x] == 7) return;
vector<int> vec;
dfs_insert(x, p, vec);
if(vec.empty()) return;
query_select(vec), query_arr[o] = query_arr[x] = 1;
if(!Ask(min(o, x), max(o, x), query_arr)) return;
int basel = 0, l, r, qa;
retry:
l = basel, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
while(l<r){
int m = (l+r)>>1;
memset(query_arr, 0, sizeof(query_arr));
query_arr[x] = query_arr[o] = 1;
vector<int> checklist;
for(int i=l; i<=m; i++){
checklist.push_back(vec[i]);
query_arr[vec[i]] = 1;
}
for(int i=0; i<(int)checklist.size(); i++){
if(par[checklist[i]] != p && !query_arr[par[checklist[i]]]){
query_arr[par[checklist[i]]] = 1;
checklist.push_back(par[checklist[i]]);
}
}
if(Ask(min(o, x), max(o, x), query_arr)){
qa = m;
r = m-1;
}
else l = m+1;
}
if(!chk[min(o, vec[qa])][max(o, vec[qa])]){
deg[o]++, deg[vec[qa]]++;
chk[min(o, vec[qa])][max(o, vec[qa])] = 1;
Answer(min(o, vec[qa]), max(o, vec[qa]));
}
for(auto nxt: link[vec[qa]]){
if(nxt == par[vec[qa]]) continue;
solve_cross(o, nxt, vec[qa]);
}
basel = qa+1;
while(basel < (int)vec.size() && depth[vec[basel]] > depth[vec[qa]]) basel++;
if(basel == (int)vec.size()) return;
goto retry;
}
void Detect(int t, int N){
n = N;
visited[0] = 1;
for(int i=1; i<n; i++){
if(visited[i]) continue;
solve(i);
}
for(int i=1; i<n; i++){
deg[i]++, deg[par[i]]++;
link[par[i]].push_back(i), link[i].push_back(par[i]);
}
for(int i=0; i<n; i++){
depth[i] = 0;
reorder(i);
for(auto j: link[i]){
for(auto k: link[j]){
if(k==i) continue;
solve_cross(i, k, j);
}
}
}
}
