#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <ctime>
#include <map>
using namespace std;
vector<pair<int, int>> T;
map<tuple<int, int, int>, int> Map;
int Ask(int a1, int a2, int a3) {
int v[3] = { a1, a2, a3 }; sort(v, v + 3);
a1 = v[0]; a2 = v[1]; a3 = v[2];
if (Map[make_tuple(a1, a2, a3)] >= 1) return Map[make_tuple(a1, a2, a3)];
int x = Query(a1, a2, a3);
Map[make_tuple(a1, a2, a3)] = x;
return x;
}
vector<int> random_shuffle(vector<int> I) {
for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
return I;
}
void dfs(vector<int> vec) {
// サイズが 1, 2, 3 のときに場合分け
if (vec.size() == 1) return;
if (vec.size() == 2) {
T.push_back(make_pair(vec[0], vec[1]));
return;
}
if (vec.size() == 3) {
int S = Ask(vec[0], vec[1], vec[2]);
if (vec[0] != S) T.push_back(make_pair(vec[0], S));
if (vec[1] != S) T.push_back(make_pair(vec[1], S));
if (vec[2] != S) T.push_back(make_pair(vec[2], S));
return;
}
vec = random_shuffle(vec);
while (true) {
// 乱択アルゴリズムで重心を見つける
int v = vec[rand() % vec.size()], cnt = 0;
for (int t = 0; t < 5; t++) {
int v1 = v, v2 = v;
while (v1 == v2 || v1 == v || v2 == v) {
v1 = vec[rand() % vec.size()];
v2 = vec[rand() % vec.size()];
}
int S = Ask(v, v1, v2);
if (S == v) cnt++;
}
if (cnt <= 1) continue;
// 連結成分ごとに分ける
vector<int>col(vec.size(), -1); int cnts = 0;
for (int t = 0; t < vec.size(); t++) {
if (col[t] >= 0 || vec[t] == v) continue;
cnts++; col[t] = cnts;
for (int j = 0; j < vec.size(); j++) {
if (col[j] >= 0 || vec[j] == v) continue;
int S = Ask(v, vec[t], vec[j]);
if (S != v) { col[j] = cnts; }
}
}
for (int t = 1; t <= cnts; t++) {
vector<int>E;
for (int j = 0; j < vec.size(); j++) {
if (col[j] == t) E.push_back(vec[j]);
}
int cur = E[0];
for (int j = 1; j < E.size(); j++) {
int F = Ask(v, cur, E[j]);
if (F == E[j]) cur = E[j];
}
T.push_back(make_pair(v, cur));
dfs(E);
}
break;
}
}
void Solve(int N) {
srand((unsigned)time(NULL));
vector<int> vec;
for (int i = 0; i < N; i++) vec.push_back(i);
dfs(vec);
for (int i = 0; i < T.size(); i++) {
if (T[i].first > T[i].second) swap(T[i].first, T[i].second);
Bridge(T[i].first, T[i].second);
}
return;
}
