Background

When submitting on Luogu, you only need to submit a single file.

Do not include alice.h and bob.h. Add the following at the top of the file:

long long setN(int n);

Only C++17 / C++20 submissions are supported.

Problem Description

Alice and Bob are famous magicians. Catherine is a wealthy person, and she really enjoys watching Alice and Bob perform magic. One day, Catherine decided to challenge Alice and Bob: as long as they can successfully perform the following magic trick, Catherine will provide them with a huge reward. The performance process is as follows:

• Step $1$: Bob enters a secret room. Throughout the whole magic trick, he can only communicate with Catherine. Next, Alice tells Catherine an integer $n$ between $2$ and $5000$.
• Step $2$: Catherine tells Alice an integer $X$ between $1$ and $10^{18}$.
• Step $3$: Alice constructs a tree with $n$ nodes and tells Catherine.
• Step $4$: Catherine deletes some edges from the tree (at most $\left\lfloor\dfrac{n-2}{2}\right\rfloor$ edges), and tells Bob the remaining edges.
• Step $5$: Based on the information given by Catherine, Bob guesses the number Catherine told Alice.

However, Alice and Bob are stumped by this magic trick, so they have to ask for your help. Please write a program that implements Alice and Bob’s strategy to help them win Catherine’s challenge.

Communication method:

You need to implement two functions.

1. std::vector<std::pair<int, int>> Alice();

• For each testdata, this function will be called only once.
• The function should return a vector of type pair<int, int>, representing the edge set of the tree that Alice constructs in Step 3.
  • Note that the nodes in the tree should be numbered starting from $1$.
  • You need to ensure that the tree returned by the function is valid, i.e., it should contain exactly $n - 1$ edges, and all nodes must be connected.

The function Alice() must call the following function exactly once:

long long setN(int n);

• This function means that in Step 1, Alice chooses a number $n$ and tells Catherine.
• The function returns a number $X$, meaning the number Catherine tells Alice in Step 2.

2. long long Bob(std::vector<std::pair<int, int>> V);

• For each testdata, this function will be called only once, and it will definitely be called after Alice().
• $V$ represents the edge set that Catherine tells Bob in Step 4.
• The above edge set is ordered. Specifically:
  • For the two endpoints of an edge, the endpoint with the smaller index comes first.
  • All edges are sorted in ascending order, using the first endpoint as the primary key and the second endpoint as the secondary key.
• The function should return an integer $X$, representing Bob’s answer in Step 5.

Input Format

None.

Output Format

None.

Hint

Example

Consider the following calls:

This example represents the following scenario:

• Step 1: At the beginning, Alice tells Catherine the number $4$.
• Step 2: Catherine tells Alice the number $3$.
• Step 3: Alice constructs a tree with $4$ nodes, whose edge set is $\{\{1, 2\}, \{2, 3\}, \{2, 4\}\}$, and tells Catherine this tree.
• Step 4: Catherine deletes the edge connecting nodes $2$ and $3$ from the tree, and tells Bob the remaining edges $\{\{1, 2\}, \{2, 4\}\}$.
• Step 5: Bob gives the number $3$ as the answer. Since he gives the correct answer, their magic show is a great success.

Subtasks

1. (5 points): $X\leq 5, 000$.
2. (30 points): $X\leq 25, 000, 000$.
3. (65 points): No special constraints.

Translated by ChatGPT 5