Xiao Ming and Xiao Hua each have a rooted tree with $n$ nodes. In Xiao Ming's tree, the parent of node $i$ is $p_i$, and the parent of the root node is $0$. In Xiao Hua's tree, the parent of node $i$ is $q_i$, and the parent of the root node is $0$. They want to know how similar their rooted trees are. To define this similarity, they have designed a "distance function" for the two rooted trees; the larger the value given by the distance function, the less similar the two trees are.

To account for both the structure of the trees and the differences in node labeling, the distance function considers pairs of nodes that have an "ancestor-descendant relationship." Specifically, in a rooted tree $T$, if two nodes $u$ and $v$ satisfy the condition that $u$ lies on the path from $v$ to the root, we call $u$ an ancestor of $v$ in $T$. If a pair of nodes $\{u, v\}$ satisfies the condition that $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$, then $\{u, v\}$ has an ancestor-descendant relationship in $T$.

Xiao Ming and Xiao Hua apply this distance function to the two trees: if a pair of nodes $\{u, v\}$ has an ancestor-descendant relationship in one tree but not in the other, they consider the distance between the two rooted trees to have increased.

However, this distance function is too rigid. To allow for some error, they introduced an error parameter $k$ to adjust the function value, involving a sub-function $d_T(u, v)$ that calculates the "ancestor-relationship distance." This means we can calculate how close two nodes $\{u, v\}$ are to "having an ancestor-descendant relationship" in a given rooted tree $T$. Obviously, when $u$ and $v$ have an ancestor-descendant relationship, their "ancestor-relationship distance" is $0$. When they do not, the ancestor-relationship distance is defined as the "minimum number of moves required for $u$ and $v$ to have an ancestor-descendant relationship." In simple terms, imagine two tokens placed on nodes $u$ and $v$; each move allows you to move a token to its parent node. The ancestor-relationship distance is the minimum number of moves such that the two tokens land on a pair of nodes that have an ancestor-descendant relationship.

Calculating the ancestor-relationship distance $d_T(u, v)$ in $T$ is straightforward: first, find the "lowest common ancestor" $\text{lca}(u, v)$ in $T$, and take the minimum of the number of steps $u$ and $v$ must move upward to reach $\text{lca}(u, v)$.

With the definition of ancestor-relationship distance, Xiao Ming and Xiao Hua's distance function can finally be defined clearly:

• First, decide on an error parameter $k$ and the two rooted trees $S$ and $T$ for which the distance is to be calculated.
• A pair of nodes $\{u, v\}$ is considered a "differing pair" if they have an ancestor-descendant relationship in one tree, while their ancestor-relationship distance in the other tree is greater than $k$.
  • That is, $(d_S(u, v) = 0 \text{ and } d_T(u, v) > k)$ or $(d_T(u, v) = 0 \text{ and } d_S(u, v) > k)$.
• Considering all $\frac{n(n-1)}{2}$ pairs of nodes, the number of differing pairs is the value of the distance function for $S$ and $T$.

The figure above shows the two rooted trees given in sample tests 1 and 2, with the left tree rooted at node 1 and the right tree rooted at node 5. Taking the pair $\{2, 5\}$ as an example, we know that in the left tree $\text{lca}(2, 5) = 1$. Moving node 5 to node 1 takes two steps, but moving node 2 to node 1 takes only one step, so their ancestor-relationship distance in the left tree is 1. Note that because the pair $\{2, 5\}$ has an ancestor-descendant relationship in the right tree, when $k=0$, the pair $\{2, 5\}$ is considered a differing pair. Similarly, the pairs $\{2, 4\}$ and $\{4, 5\}$ are also differing pairs. Therefore, the distance function value for the two trees in the figure at $k=0$ is 3. When $k=1$, only $\{4, 5\}$ is considered a differing pair because its ancestor-relationship distance in the left tree is 2, so the distance function value is only 1.

Please write a program to help Xiao Ming and Xiao Hua calculate the distance function value for two given rooted trees with an error parameter $k$.

Input

• $n$ $k$
• $p_1$ $p_2$ $\dots$ $p_n$

• $q_1$ $q_2$ $\dots$ $q_n$

• $n$ represents the size of the given trees.

• $k$ represents the error parameter used for measuring the distance between the two trees.
• In the first given tree, the parent of node $i$ is $p_i$. Specifically, $p_i = 0$ indicates that node $i$ is the root of the first tree.
• In the second given tree, the parent of node $i$ is $q_i$. Specifically, $q_i = 0$ indicates that node $i$ is the root of the second tree.

Output

• $d$

• $d$ is an integer representing the distance function value of the two given trees at error parameter $k$.

Constraints

• $1 \le n \le 2 \times 10^5$.
• $0 \le k < n$.
• $0 \le p_i, q_i \le n$.
• It is guaranteed that there exists a unique $u$ such that $p_u = 0$, and the sequence $p$ forms a rooted tree with $u$ as the root.
• It is guaranteed that there exists a unique $v$ such that $q_v = 0$, and the sequence $q$ forms a rooted tree with $v$ as the root.
• All input numbers are integers.

Examples

Input 1

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

Output 1

3

Input 2

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

Output 2

1

Input 3

10 0
6 5 5 5 0 3 4 6 6 6
6 4 5 7 10 7 10 7 3 0

Output 3

22

Input 4

10 2
0 1 2 3 4 5 6 7 8 9
8 7 6 5 0 5 4 3 2 1

Output 4

6

Subtasks