#include <bits/stdc++.h>
#ifndef skeletaZaPrezident
#include "meetings.h"
#endif
#define query Query
#define bridge Bridge
#define solve Solve
#define int32_t int
#define int64_t long long
const int32_t MAX_N = 2000;
#ifdef skeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w) {
std::cout << u << " " << v << " " << w << '\n' << std::flush;
int32_t res;
std::cin >> res;
return res;
}
void bridge(int32_t u, int32_t v) {
std::cout << "edge: " << u << " " << v << '\n' << std::flush;
}
#endif
#ifndef sekeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w);
void bridge(int32_t u, int32_t v);
#endif
std::map< int32_t, int32_t > asked[MAX_N + 5][MAX_N + 5];
int32_t ask_query(int32_t x, int32_t y, int32_t z) {
int32_t a[] = { x, y, z };
std::sort(a, a + 3);
if(asked[a[0]][a[1]].count(a[2]) == 0) {
asked[a[0]][a[1]][a[2]] = query(a[0], a[1], a[2]);
}
return asked[a[0]][a[1]][a[2]];
}
struct Vertex {
bool vis;
int32_t subtreeSize;
std::vector< int32_t > adjList;
Vertex() : vis(false), subtreeSize(1) {}
};
bool isInserted[MAX_N + 5];
Vertex t[MAX_N + 5];
bool sort_by_subtree_size(int32_t u, int32_t v) {
return t[u].subtreeSize > t[v].subtreeSize;
}
void init(int32_t n) {
for(int32_t i = 0; i < n; i++) {
t[i].vis = false;
}
}
void compute_subtree_sizes(int32_t v, int32_t par) {
t[v].subtreeSize = 1;
for(auto &x : t[v].adjList) {
if(x == par || t[x].vis) {
continue;
}
compute_subtree_sizes(x, v);
t[v].subtreeSize += t[x].subtreeSize;
}
}
int32_t find_centroid(int32_t v, int32_t par, int32_t target) {
int32_t maxSubtree = -1, ind = -1;
for(auto &x : t[v].adjList) {
if(x == par || t[x].vis) {
if(t[x].vis) {
t[x].subtreeSize = 0;
}
continue;
}
if(t[x].subtreeSize > maxSubtree) {
maxSubtree = t[x].subtreeSize;
ind = x;
}
}
if(ind != -1 && maxSubtree > target / 2) {
return find_centroid(ind, v, target);
}
return v;
}
void solve_vertex(int32_t root, int32_t v) {
compute_subtree_sizes(root, -1);
int32_t centroid = find_centroid(root, -1, t[root].subtreeSize);
compute_subtree_sizes(centroid, -1);
int32_t aux;
std::sort(t[centroid].adjList.begin(), t[centroid].adjList.end(), sort_by_subtree_size);
for(int32_t i = 0; i < (int32_t) t[centroid].adjList.size(); i++) {
if(i == (int32_t) t[centroid].adjList.size() - 1) {
aux = ask_query(centroid, t[centroid].adjList[i], v);
if(aux == v) {
t[t[centroid].adjList[i]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
if(aux == t[centroid].adjList[i]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i], v);
return;
}
if(aux != centroid) {
solve_vertex(aux, v);
t[t[centroid].adjList[i]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
isInserted[aux] = true;
return;
}
break;
}
aux = ask_query(t[centroid].adjList[i], t[centroid].adjList[i + 1], v);
// v is on the path from t[centroid].adjList[i] to t[centroid].adjList[i + 1]
if(aux == v) {
aux = ask_query(t[centroid].adjList[i], centroid, v);
if(aux == centroid) {
t[t[centroid].adjList[i + 1]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i + 1]);
t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
t[t[centroid].adjList[i]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
if(aux == t[centroid].adjList[i]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i], v);
return;
}
if(aux == t[centroid].adjList[i + 1]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i + 1], v);
return;
}
if(aux != centroid) {
solve_vertex(aux, v);
int32_t aux2 = ask_query(t[centroid].adjList[i], aux, centroid);
if(aux2 == centroid) {
t[t[centroid].adjList[i + 1]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i + 1]);
t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
}
else {
t[t[centroid].adjList[i]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
}
isInserted[aux] = true;
return;
}
}
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
}
void solve(int32_t n) {
t[0].adjList.push_back(1);
t[1].adjList.push_back(0);
// solve for each node
for(int32_t i = 2; i < n; i++) {
if(isInserted[i]) {
continue;
}
init(n);
solve_vertex(0, i);
}
for(int32_t i = 0; i < n; i++) {
for(auto &x : t[i].adjList) {
if(x > i) {
bridge(i, x);
}
}
}
}
