题目背景

前几天 一年前 CCD 因为模拟赛挂分而被 _Eriri_ 嘲讽，于是他准备出一道题来嘲讽 _Eriri_。

栋皇重色思倾国，御宇多年求不得。

蒋家有女初长成，养在深闺人未识。

天生丽质难自弃，一朝选在君王侧。

回眸一笑百媚生，六宫粉黛无颜色。

[upd 2025/5/5]. <- 链接赛前一天被 _Eriri_ 删除……

题目描述

请注意，此题仅支持 C++11 及以上提交！

栋明皇有一棵非常神秘的有 $n$ 个点的有根树 $T$，根为 $1$。

而你，作为尊贵的蒋贵妃，非常想知道树 $T$ 的形态，但你每次只能向栋明皇问一个二元组 $(i,j)\ (1 \le i , j \le n)$，栋明皇会告诉你这两个点在树上的最近公共祖先 $k$。由于栋明皇还要忙着筹备 Opoi，他只允许你向他问 $n \times 300$ 次问题。

幸运的是，栋明皇喜欢紧凑的结构，所以这颗树的叶子个数至多为 $20$。

本题是一道交互题。

提交时，请在程序中加入以下函数声明语句：

int LCA(int,int);

这使你可以调用 LCA(x,y) 并得到它们的 LCA。

你不需要，也不应该实现主函数，你只需要实现下列函数：

vector<pair<int, int> > guess(int n);

• 每个测试点交互库只会调用一次该函数。
• 其中 $n$ 表示本次猜测的树 $T$ 的结点个数。
• 返回的 vector 描述了树 $T$ 的结构，其中 vector 的每一个 pair<int, int> 表示树的一条边 $(u,v)$，每条边两个节点的顺序和边与边之间的顺序没有要求。
• 单次 LCA(x, y) 复杂度是严格 $O(1)$ 的，交互库预处理复杂度 $O(n \log_2 n)$。
• SPJ 不会因你 LCA 的调用次数过多返回 WA，但如果超过了 $n \times 300$ 次，那么后面的 LCA 调用结果都是 -1。

题目附件里有一个示范模板 template.cpp，使用它你可以获得 $0$ 分的好成绩。

2

1 2

提示

样例解释

You	Interactor
LCA(1,2)	1
1 2	Accepted

除了样例输出，输出 2 1 也是一个合法的解。

---

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^4$。

部分分：数据共有 $20$ 组，对于第 $i$ 组数据，保证树的叶子个数至多为 $i$。

---

提示

如果你不知道怎么解决交互题，可以参考这题。

本题模板程序与模板交互库见附件中的 template.cpp 与 s_interactor.cpp。