Cat Exercise

문제

There are $NN$ cat towers, numbered from $11$ to $NN$. The height of Tower $ii$ (1 ≤ i ≤ N) is $P_{i}P\_i$. The heights of the towers are distinct integers between $11$ and $NN$, inclusive. There are $N-1N\; -\; 1$ adjacent pairs of towers. For each $jj$ (1 ≤ j ≤ N - 1), Tower $A_{j}A\_j$ and Tower $B_{j}B\_j$ are adjacent to each other. In the beginning, it is possible to travel from a tower to any other tower by repeating moves from towers to adjacent towers.

In the beginning, a cat stays in a tower of height $NN$.

Then we perform cat exercises. In cat exercises, we repeatedly choose a tower and put an obstacle on it. However, we cannot put an obstacle on a tower where we already put an obstacle on it. During the process, the following will happen.

• If the cat does not stay in the chosen tower, nothing will happen.
• If the cat stays in the chosen tower and there is an obstacle on every tower which is adjacent to the chosen tower, the cat exercises will finish.
• Otherwise, among the towers where the cat can arrive by repeating moves from towers to adjacent towers without obstacles, the cat will move to the highest tower except for the current tower by repeating moves from towers to adjacent towers. In this process, the cat takes the route where the number of moves from towers to adjacent towers becomes minimum.

Given information of the heights of the towers and pairs of adjacent towers, write a program which calculates the maximum possible sum of the number of moves of the cat from towers to adjacent towers if we put obstacles suitably

입력

Read the following data from the standard input.

$NN$

$P_{1}P\_1$ $P_{2}P\_2$ $\cdots \backslash cdots$ $P_{N}P\_N$

$A_{1}A\_1$ $B_{1}B\_1$

$A_{2}A\_2$ $B_{2}B\_2$

$\mathrm{⋮}\backslash vdots$

$A_{N-1}A\_\{N-1\}$ $B_{N-1}B\_\{N-1\}$

출력

Write one line to the standard output. The output should contain the maximum possible sum of the number of moves of the cat from towers to adjacent towers.

4
3 4 1 2
1 2
2 3
3 4

3

7
3 2 7 1 5 4 6
1 2
1 3
2 4
2 5
3 6
3 7

7