This is an interactive problem.

Problem Background

Deep within the cave, the moss-covered ancient walls trembled violently, kicking up a cloud of dust, before the heavy gate slowly slid to both sides.

The air inside the gate, freed from its century-long confinement, rushed out to meet its old friends, catching Altar off guard and knocking him two meters away.

Replacing the extinguished torch, the brilliant glow emanating from the gemstones surrounding the altar provided light for Altar.

Description

The altar is a regular $n$-gon with a gemstone at each vertex. There are $n$ types of gemstones corresponding one-to-one with $n$ types of energy, labeled with integers from $1$ to $n$. The energy labels are not necessarily assigned in the order of the gemstones around the $n$-gon.

Among the $n$ types of energy, there are $(2n-3)$ bidirectional energy links. These energy links correspond to the gemstones and form exactly a regular $n$-gon and one of its triangulations. That is:

• Every energy link connects two different energies, and no two energy links connect the same pair of energies;
• There is always an energy link between the energies corresponding to two adjacent gemstones on the altar;
• Furthermore, if line segments are drawn between the gemstones corresponding to the two energies connected by an energy link, no two segments intersect except at their endpoints, and they divide the altar into $(n-2)$ triangles.

Altar only knows the value of $n$; he does not know which energy corresponds to which gemstone, nor does he know which energies are connected by energy links.

Initially, all energy links are undestroyed. Altar needs to change the state of all $(2n-3)$ links to destroyed. To do this, Altar can perform the following operations, each requiring the selection of two energies $1 \le i, j \le n$:

1. Energy Sensing: Obtain the minimum number of undestroyed energy links required to connect $i$ and $j$; that is, treating gemstones as nodes and undestroyed energy links as undirected edges with weight $1$, find the shortest path length between $i$ and $j$. If $i$ and $j$ are not connected, the result is $(n+1)$.
2. Link Destruction: Requires that there is an energy link between $i$ and $j$ and its state is undestroyed, then changes its state to destroyed.
3. Link Reconstruction: Requires that there is an energy link between $i$ and $j$ and its state is destroyed, then changes its state to undestroyed. Due to the high physical exertion, Altar cannot use the link reconstruction operation more than $(2n-3)$ times.

You need to help Altar complete this task. The number of times you use Energy Sensing determines Altar's destruction efficiency (and thus your score).

Implementation Details

Please ensure your program starts with #include "altar.h".

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

void altar(int n);

• Here, $n$ represents the number of sides of the altar.

You can call the following functions:

int sense(int i, int j);
bool destroy(int i, int j);
void reconstruct(int i, int j);

• These three functions represent the Energy Sensing, Link Destruction, and Link Reconstruction operations, respectively. You must ensure $1 \le i, j \le n$.
  • For the sense function, it returns the shortest path length between $i$ and $j$; if they are not connected, it returns $(n+1)$. You must ensure the number of calls to sense does not exceed $5 \times 10^5$.
  • For the destroy function, if all energy links are in the destroyed state after this operation, it returns true, otherwise it returns false.
  • For the reconstruct function, you must ensure the total number of calls does not exceed $(2n-3)$.

Under the conditions and constraints of the problem, the interactive library will run within 1500 ms and use no more than 64 MiB of memory.

The interactive library is not adaptive; that is, the energy links and the energy label corresponding to each gemstone are fixed and will not change during the interaction.

Testing Your Program

The grader.cpp in the problem directory is our provided reference implementation of the interactive library. You may ignore the differences between the implementation used for final testing and this reference, but you should not attack the interactive library.

You need to compile your program using the following command in the problem directory:

g++ grader.cpp sample.cpp -o sample -O2 --std=c++14 -lm

For the compiled executable:

• The executable will read the following data from standard input:
  • The first line contains an integer $n$, the number of sides of the altar.
  • The next line contains $n$ integers $p_1, p_2, \dots, p_n$, representing the energy labels of the gemstones in clockwise order. You must ensure this is a permutation of $1$ to $n$.
  • The next $(n-3)$ lines each contain two integers $i, j$, representing an energy link. You do not need to input energy links of the form $(p_k, p_{(k \bmod n) + 1})$.
• After reading is complete, the interactive library will call the function altar exactly once.
• After the altar function exits, if all your calls within the function satisfy the problem conditions and all energy links have been destroyed, the interactive library will output Correct. X, where $X$ is the number of calls to sense; otherwise, it will output the corresponding error message.

Examples

Input

4
1 3 2 4
3 4

Output

Correct. 0

Note

The output above is the output of the provided sample program for this test case.

In this example, the energy labels for each gemstone and the energy links are shown in the figure below.

Subtasks

For all test data, $3 \le n \le 10^{3}$.

• Subtask 1 (10 points): There exists an energy that has a link with all other energies.
• Subtask 2 (10 points): After removing the links of the $n$-gon, the remaining links form a chain of length $(n-3)$.
• Subtask 3 (30 points): This subtask contains 5 test cases, generated as follows:
  • $n = 10^{3}$, $p_1, \dots, p_n$ are generated uniformly at random from all possible permutations;
  • The triangulation is generated as follows: for a convex polygon, if the number of points is $\le 3$, terminate; otherwise, randomly choose two non-adjacent vertices, connect them with an edge, and recursively process the two convex polygons created by this edge.
• Subtask 4 (50 points): No additional restrictions. This subtask depends on Subtasks 1, 2, and 3.

Scoring

For each test case, if your program encounters a runtime error, exceeds time or memory limits, makes an illegal function call, or fails to destroy all energy links upon function termination, you will receive $0\%$ of the score for that test case. Otherwise, your score percentage for the test case will be calculated based on the number of sense calls $X$ using the following formula:

• If $X \in (10^5, 5 \times 10^5]$, you receive $\left(5 + 15 \times \frac{5 \times 10^5 - X}{4 \times 10^5}\right) \%$ of the score;
• If $X \in (10500, 10^5]$, you receive $\left(20 + 30 \times \frac{10^5-X}{89500}\right) \%$ of the score;
• If $X \in (3500, 10500]$, you receive $\left(50 + 75 \times \left(\frac{3500}{X} - \frac{1}{3}\right)\right) \%$ of the score;
• If $X \le 3500$, you receive $100\%$ of the score for that test case.

The score for each subtask is the minimum score percentage among all test cases in that subtask multiplied by the total points for that subtask.

Postscript

After destroying the last pair of energy links, the trembling earth and falling stones triggered Altar's survival instinct.

Altar escaped just before the cave collapsed. Looking around, the sleeping forest remained undisturbed, as if nothing had happened.

Altar just smiled slightly: it was just like always, the world simply forgot to respond.