Magic Communication Challenge

Alice and Bob are two famous magicians, and they have been challenged by the wealthy Catherine. Catherine loves watching their magic tricks and has proposed a challenge: if they can perform the following magic trick, she will award them a huge prize!

The magic trick is performed in the following steps:

1. Step 1: Bob enters a sealed room and can only communicate with Catherine during the magic trick. Meanwhile, Alice tells Catherine an integer \(n\) such that \(2 \leq n \leq 5000\).
2. Step 2: Catherine tells Alice an integer \(X\) satisfying \(1 \leq X \leq 10^{18}\).
3. Step 3: Alice generates a tree with \(n\) nodes (nodes numbered from 1 to \(n\)) and tells Catherine the set of edges of the tree. A valid tree has exactly \(n-1\) edges and is connected.
4. Step 4: Catherine removes some edges from the tree (at most \(\left\lfloor\frac{n-2}{2}\right\rfloor\) edges) and sends the remaining set of edges to Bob. The edge set is ordered such that for each edge, the smaller endpoint comes first, and the list is sorted lexicographically by the endpoints.
5. Step 5: Bob, based solely on the information given by Catherine in Step 4, must guess the number \(X\) that Catherine originally sent to Alice.

Alice and Bob were stumped by this challenge and have turned to you for help. Implement a strategy via two functions according to the following communication protocol, so they may win Catherine’s challenge.

Communication Protocol:

• Alice Function: Implement a function std::vector<std::pair<int, int>> Alice(); which is called exactly once per test case. This function should call long long setN(int n); exactly once to inform Catherine of the chosen \(n\) and receive the integer \(X\). Then, construct and return the edge set of a valid tree with \(n\) nodes.
• Bob Function: Implement a function long long Bob(std::vector<std::pair<int, int>> V); which is called after Alice() and receives the (possibly reduced) edge set \(V\) (which meets the ordering requirements described above). This function should return the integer \(X\) as Bob’s guess.

Note: Your solution must work in a way that guarantees Bob can always correctly determine \(X\) regardless of the edge removals performed by Catherine (subject to the allowed limit).

Hint: A simple strategy is to choose \(n = 2\). In this case, the tree has a single edge and Catherine is not allowed to remove any edges. You can then store \(X\) in a global variable when setN is called, and simply return it in Bob().

inputFormat

The input consists of a single integer (X) ((1 \leq X \leq 10^{18})) provided by Catherine.

outputFormat

Output a single integer (X), which is Bob's guess of the number provided by Catherine.

sample

42

42