Background

A few days ago One year ago, CCD lost points in a mock contest and got mocked by Eriri, so he decided to make a problem to mock Eriri back.

The emperor loved beauty and longed for a lady who could topple a nation, yet after ruling for many years he could not find one.

In the Jiang family there was a girl just grown up, kept in the inner chambers, unknown to others.

Born with natural beauty that could not be ignored, one day she was chosen to stand by the ruler.

Looking back with a smile, a hundred charms appeared; the makeup of the six palaces all lost their color.

[upd 2025/5/5]. <- The link was deleted by Eriri the day before the contest…

Problem Description

Please note: this problem only supports submissions in C++11 or above.

Emperor Dong has a very mysterious rooted tree $T$ with $n$ nodes, with root $1$.

And you, as the noble Consort Jiang, really want to know the shape of tree $T$. However, each time you can only ask Emperor Dong one ordered pair $(i,j)\ (1 \le i , j \le n)$, and he will tell you the lowest common ancestor $k$ of these two nodes in the tree. Since Emperor Dong is also busy preparing for Opoi, he only allows you to ask $n \times 300$ questions.

Luckily, Emperor Dong likes compact structures, so the number of leaves of this tree is at most $20$.

This is an interactive problem.

When submitting, please add the following function declaration in your program:

int LCA(int,int);

This allows you to call LCA(x,y) and get their LCA.

You do not need to, and should not, implement the main function. You only need to implement the following function:

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

• For each test point, the interactive library will call this function only once.
• Here, $n$ is the number of nodes of the tree $T$ to be guessed this time.
• The returned vector describes the structure of tree $T$. Each pair<int, int> in the vector represents an edge $(u,v)$ of the tree. There is no requirement on the order of the two nodes in each edge, nor on the order of the edges.
• The time complexity of a single LCA(x, y) call is strictly $O(1)$, and the interactive library preprocessing complexity is $O(n \log_2 n)$.
• The SPJ will not return WA because you called LCA too many times, but if you exceed $n \times 300$ calls, then all subsequent LCA call results will be -1.

There is a sample template template.cpp in the attachments. Using it, you can get a good score of $0$ points.

Output Format

Hint

Sample Explanation

Besides the sample output, outputting 2 1 is also a valid solution.

Constraints and Conventions

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$.

Partial score: there are $20$ groups of testdata in total. For the $i$-th group, it is guaranteed that the number of leaves of the tree is at most $i$.

2

1 2

Hint

Sample Explanation

Besides the sample output, outputting 2 1 is also a valid solution.

Constraints and Conventions

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$.

Partial score: there are $20$ groups of testdata in total. For the $i$-th group, it is guaranteed that the number of leaves of the tree is at most $i$.

Hint

If you do not know how to solve interactive problems, you can refer to this problem.

The template program and the template interactive library for this problem can be found in the attachments: template.cpp and s_interactor.cpp.

Translated by ChatGPT 5