Description

The Federation has $N$ planets, and the new administrative structure is a binary tree. The administrative center of the Federation is the capital. All other planets are divided into at most two regions, and inside each region the structure is the same.

Before this administrative reform, each planet stationed a space fleet. The combat power of the fleet stationed on planet $i$ is $F_i$.

During the reform, the Space Defense Council needs to adjust the stationed locations of fleets to satisfy the military rule that the fleet stationed at the center of each administrative region must be the strongest fleet (by combat power) within that region. Also, according to the military rules, there is only one way to adjust fleet locations: the fleets of two planets swap their stations. Now, there are $M$ bidirectional interstellar routes between planets. Only two planets connected by an interstellar route can swap fleets.

To save expenses, the council wants the total number of swaps to be as small as possible. Early this year, the council commissioned Xiao Cheng to make a swapping plan, but he still has not finished it. Can you help him so that he can avoid being dismissed?

Input Format

The first line contains two integers $N, M$ separated by spaces.

The second line contains $N$ integers $R_1, R_2, \ldots, R_N$ separated by spaces. $R_i$ denotes the index of the direct superior planet of planet $i$. For the capital of the Federation, $R_i$ is $0$.

The third line contains $N$ pairwise distinct integers $F_1, F_2, \ldots, F_N$ separated by spaces. Here $F_i$ denotes the combat power of the fleet currently stationed on planet $i$.

The next $M$ lines each contain two integers $X_i, Y_i$, indicating that there is an interstellar route between planets $X_i$ and $Y_i$.

The input guarantees that the administrative relationships between planets form a binary tree, that there is at most one interstellar route between any two planets, and that there are no self-loops.

The testdata guarantees that a solution exists.

Output Format

Output one line with one integer, the minimum total number of swaps.

4 4
0 1 2 3
1 2 3 4
1 2
1 4
2 3
1 3

2

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 12$, $1 \le M \le 20$, $1 \le F_i \le 100$.

Translated by ChatGPT 5