#include "park.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int Ask(int A , int B , int Place[]);
void Answer(int A , int B);
const int NMAX = 2000 + 7;
int n;
int places[NMAX];
int vis[NMAX];
vector<int> g[NMAX];
bool rem[NMAX], in[NMAX];
void add_edge(int s, int t) {
if (s > t) swap(s, t);
Answer(s, t);
g[s].push_back(t);
g[t].push_back(s);
}
bool query(int s, int t) {
if (s > t) swap(s, t);
assert(places[s] == 1);
assert(places[t] == 1);
return Ask(s, t, places);
}
bool direct(int u) {
for (int i = 0; i < n; ++i) {
places[i] = (vis[i] == 1);
}
places[u] = 1;
return query(0, u);
}
int get_next(int u) {
int l = 0, r = n - 1, sol = -1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i <= m; ++i) {
places[i] = (vis[i] != 2);
}
for (int i = m + 1; i < n; ++i) {
places[i] = (vis[i] == 1);
}
places[u] = true;
if (query(0, u)) {
sol = m;
r = m - 1;
} else {
l = m + 1;
}
}
return sol;
}
void clear(int u) {
rem[u] = false;
for (auto v : g[u]) {
if (rem[v]) {
clear(v);
}
}
}
vector<int> nodes;
void dfs(int u) {
nodes.push_back(u);
in[u] = 1;
for (auto v : g[u]) {
if (rem[v] && !in[v]) {
dfs(v);
}
}
}
void find_edge(int u) {
for (int i = 0; i < n; ++i) {
rem[i] = (vis[i] == 1);
}
for (int root = 0; root < n; ++root) {
while (rem[root]) {
for (int i = 0; i < n; ++i) {
places[i] = rem[i];
}
places[u] = 1;
if (!query(u, root)) {
clear(root);
continue;
}
nodes.clear();
for (int i = 0; i < n; ++i) {
in[i] = false;
}
dfs(root);
int l = 0, r = nodes.size() - 1, sol = -1;
while (l <= r) {
int m = (l + r) / 2;
for (int i = 0; i < nodes.size(); ++i) {
places[nodes[i]] = (i <= m);
}
if (query(root, u)) {
sol = m;
r = m - 1;
} else {
l = m + 1;
}
}
add_edge(u, nodes[sol]);
rem[nodes[sol]] = false;
}
}
}
void add(int u) {
vis[u] = 2;
while (!direct(u)) {
add(get_next(u));
}
find_edge(u);
vis[u] = 1;
}
void Detect(int T, int N) {
n = N;
vis[0] = 1;
for (int i = 1; i < n; ++i) {
if (!vis[i]) {
add(i);
}
}
}
/**
#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) WA(10);
// if (A >= B) WA(11);
// if (B >= N) WA(12);
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];
}
int main(int argc, char **argv) {
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);
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");
return 0;
}
**/
