#include "meetings.h"
#include <vector>
#include <algorithm>
using namespace std;
vector<int> G[2009];
vector<int> I, J1, J2;
bool passed[2009];
bool forced[2009];
void dfs(int pos) {
passed[pos] = true; int cnts = 0;
for (int i = 0; i < G[pos].size(); i++) {
if (passed[G[pos][i]] == true) continue;
dfs(G[pos][i]); cnts++;
}
if (cnts == 0) I.push_back(pos);
}
void dfs2(int pos, int to) {
if (pos == to) { J2 = J1; return; }
passed[pos] = true;
for (int i = 0; i < G[pos].size(); i++) {
if (passed[G[pos][i]] == true) continue;
J1.push_back(G[pos][i]);
dfs2(G[pos][i], to);
J1.pop_back();
}
}
vector<int> getpath(int u, int v) {
J1.clear(); J2.clear();
J1.push_back(u);
dfs2(u, v);
return J2;
}
int getlca(int root, vector<pair<int, int>> E) {
vector<int> cand; I.clear();
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].first);
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].second);
for (int i : cand) G[i].clear();
for (int i : cand) passed[i] = false;
for (int i : cand) forced[i] = false;
for (int i = 0; i < E.size(); i++) {
G[E[i].first].push_back(E[i].second);
G[E[i].second].push_back(E[i].first);
}
dfs(E[0].first);
if (G[E[0].first].size() == 1) I.push_back(E[0].first);
int mi = I.size() / 2;
for (int i = mi; i < I.size(); i++) {
int R = Query(root, I[i - mi], I[i]);
for (int j : cand) passed[j] = false;
vector<int> C1 = getpath(I[i - mi], R);
for (int j = 0; j < C1.size() - 1; j++) forced[C1[j]] = true;
for (int j : cand) passed[j] = false;
vector<int> C2 = getpath(I[i], R);
for (int j = 0; j < C2.size() - 1; j++) forced[C2[j]] = true;
}
for (int i : cand) {
if (forced[i] == false) return i;
}
return -1;
}
vector<pair<int, int>> dfs(vector<int> A) {
if (A.size() == 1) {
return vector<pair<int, int>>{};
}
if (A.size() == 2) {
return vector<pair<int, int>>{make_pair(A[0], A[1])};
}
// 重心っぽい頂点を見つける
int grav = -1;
while (true) {
int s = rand() % A.size(), cnt = 0; bool flag = false;
for (int i = 1; i <= 10; i++) {
int t = -1, u = -1;
while (A[s] == t || t == u || A[s] == u) {
t = A[rand() % A.size()];
u = A[rand() % A.size()];
}
if (Query(A[s], t, u) == A[s]) cnt++;
if (i == 5 && cnt <= 0) { flag = true; break; }
if (i == 7 && cnt <= 1) { flag = true; break; }
if (i == 10 && cnt <= 2) { flag = true; break; }
}
if (flag == false) { grav = s; break; }
}
// 重心分解をする
vector<bool> used(A.size(), 0);
used[grav] = true; int rem = A.size() - 1;
vector<vector<int>> centroid;
while (rem > 0) {
int p = -1;
while (p == -1 || used[p] == true) {
p = rand() % A.size();
}
vector<int> cand; cand.push_back(A[p]); used[p] = true; rem--;
for (int i = 0; i < A.size(); i++) {
if (used[i] == true || i == p) continue;
if (Query(A[grav], A[p], A[i]) != A[grav]) { cand.push_back(A[i]); used[i] = true; rem--; }
}
centroid.push_back(cand);
}
// 復元をする
vector<pair<int, int>> ans;
for (vector<int> f : centroid) {
vector<pair<int, int>> Z = dfs(f);
for (pair<int, int> i : Z) ans.push_back(i);
int U = f[0];
if (Z.size() >= 1) U = getlca(A[grav], Z);
ans.push_back(make_pair(A[grav], U));
}
return ans;
}
void Solve(int N) {
vector<int> L;
for (int i = 0; i < N; i++) L.push_back(i);
vector<pair<int, int>> V = dfs(L);
for (int i = 0; i < V.size(); i++) {
if (V[i].first > V[i].second) swap(V[i].first, V[i].second);
Bridge(V[i].first, V[i].second);
}
return;
}
