#include <bits/stdc++.h>
#include "park.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
/*
#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) {
cout << "Wrong Answer " << wa_num << "\n";
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];
}
*/
//-----------------------------
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int val(int x) {
uniform_int_distribution <int> rnd(0, x-1);
return rnd(rng);
}
static int Place[1400];
int n, tim, m;
int bio[1400], dis[1400], st[1400], en[1400], wh[1400];
bool ban[1400][1400];
vector <int> adj[1400];
void dfs(int x, int p = -1) {
for (auto y : adj[x]) {
if (y == p) continue;
dis[y] = dis[x] + 1;
dfs(y, x);
}
}
void dfs2(int x, int p = -1) {
wh[tim] = x;
st[x] = tim++;
for (auto y : adj[x]) {
if (y == p) continue;
dfs2(y, x);
}
en[x] = tim-1;
}
void ans(int x, int y) {
if (x > y) swap(x, y);
if (ban[x][y]) return;
ban[x][y] = 1;
Answer(x, y);
m++;
if (m >= n) return;
adj[x].pb(y);
adj[y].pb(x);
bio[x] = bio[y] = 1;
}
int ask(int x, int y) {
if (x > y) swap(x, y);
return Ask(x, y, Place);
}
void rek(int x, int y) {
for (int i = 0; i < n; i++) Place[i] = 0;
if (x > y) swap(x, y);
Place[x] = Place[y] = 1;
if (ask(x, y)) {
ans(x, y);
return;
}
vector <int> v;
for (int i = 0; i < n; i++) {
if (i == x || i == y || bio[i]) continue;
Place[i] = 1;
v.pb(i);
}
int lo = 0, hi = n-3;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
for (int i = mid; i < v.size(); i++) Place[v[i]] = 0;
if (ask(x, y)) hi = mid-1;
else lo = mid;
for (int i = mid; i < v.size(); i++) Place[v[i]] = 1;
}
rek(x, v[lo]);
rek(v[lo], y);
}
void rec(int x, int y) {
for (int i = 0; i < n; i++) Place[i] = 0;
Place[x] = 1;
for (int i = st[y]; i <= en[y]; i++) Place[wh[i]] = 1;
if (!ask(x, y)) return;
int lo = st[y], hi = en[y];
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int i = 0; i < n; i++) Place[i] = 0;
Place[x] = 1;
for (int i = st[y]; i <= mid; i++) Place[wh[i]] = 1;
if (ask(x, y)) hi = mid;
else lo = mid+1;
}
int z = wh[lo];
ans(x, z);
for (auto it : adj[z]) {
if (st[it] < st[z]) continue;
rec(x, it);
}
}
void Detect(int T, int N) {
n = N;
if (N == 2) {
Answer(0, 1);
return;
}
bio[0] = 1;
while (1) {
vector <int> v;
for (int i = 0; i < n; i++) if (!bio[i]) v.pb(i);
if (v.empty()) break;
shuffle(all(v), rng);
int x = v[0];
dis[0] = 0;
dfs(0);
int lo = 0, hi = 0;
for (int i = 0; i < n; i++) if (bio[i]) hi = max(hi, dis[i]);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
for (int i = 0; i < n; i++) Place[i] = (!bio[i] || dis[i] < mid);
if (!ask(0, x)) lo = mid;
else hi = mid-1;
}
int d = lo;
if (!d) {
rek(0, x);
continue;
}
v.clear();
for (int i = 0; i < n; i++) if (bio[i] && dis[i] == d) v.pb(i);
lo = 0; hi = v.size()-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int i = 0; i < n; i++) Place[i] = 1;
for (int i = mid+1; i < v.size(); i++) Place[v[i]] = 0;
if (ask(0, x)) hi = mid;
else lo = mid+1;
}
rek(v[lo], x);
}
for (int i = 0; i < n; i++) {
for (auto x : adj[i]) {
tim = 0;
dfs2(x, i);
for (auto y : adj[x]) {
if (y == i) continue;
rec(i, y);
}
}
}
}
//-----------------------------
/*
int main(int argc, char **argv) {
int i;
cin >> T >> N >> M;
Answertotal = 0;
for(i = 0 ; i < N ; i++) degree[i] = 0;
for(i = 0 ; i < M ; i++) {
int ea,eb;
cin >> ea >> eb;
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);
cout << "Accepted\n";
return 0;
}*/
