Background

FanFan is not satisfied with building only a deep-blue tree. He thinks a tree with only deep blue is too monotonous, so he wants to dye this tree with colors.

Problem Description

Since it is now the fantasy Year of the Dragon, FanFan’s deep-blue tree has been dyed with colors, and the color of node $i$ is $a_i$.

FanFan is someone who changes his mind easily. In the next $q$ days, he will change the colors he likes every day. On day $i$, the two colors he likes are $x_i, y_i$ ($x_i \neq y_i$).

But to take care of his tree, he needs to move on the tree often, and he will only pass through colors he likes.

Specifically, on day $i$, FanFan will choose an ordered pair of nodes $(u,v)$, then move along the unique simple path $u \to v$, and all nodes on the path (including $u$ and $v$) must have colors in $\{x_i, y_i\}$ ($u$ may be equal to $v$). After that, he can do one Yoimiya pull.

Every day, you need to pull a C6 Yoimiya, and then tell FanFan how many possible ordered node pairs he can choose.

Input Format

The first line contains two positive integers $n, q$.

The next line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the color of each node.

The next line contains $n-1$ positive integers $p_2, p_3, \cdots, p_n$, meaning that for all $2 \le i \le n$, there is an edge $(p_i, i)$ in the tree.

The next $q$ lines each contain two positive integers $x_i, y_i$.

Output Format

For each query, output one positive integer per line representing the answer.

5 3
1 2 1 3 3
1 1 2 2
1 2
1 3
2 3

9
6
9

Hint

Sample $1$ Explanation

The shape of the tree is shown in the figure:

For the first query, the only valid paths are paths from one node to another among $\{1,2,3\}$.

For the second query, the only valid paths are $1 \to 1, 1 \to 3, 3 \to 1, 3 \to 3, 4 \to 4, 5 \to 5$.

Subtask Constraints

This problem uses bundled subtasks.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le q \le 2 \times 10^6$, $1 \le a_i, x, y \le n$, $x \neq y$. It is guaranteed that $p_i < i$.

Special Property A: $p_i = 1$.

Special Property B: $p_i = i - 1$.

Translated by ChatGPT 5