Given two trees $T_1$ and $T_2$ with the same vertex set $\{1, 2, \dots, n\}$, find the number of non-empty subsets of vertices that form a path in both $T_1$ and $T_2$.
A subset of vertices $S$ forms a path in $T_i$ if and only if there exist $1 \le x \le y \le n$ such that the set of vertices on the shortest path between $x$ and $y$ in $T_i$ is exactly $S$.
Input
The first line contains an integer $n$.
The next two lines each contain $n-1$ integers. Assuming the root of both $T_1$ and $T_2$ is $1$, the $j$-th integer in the $i$-th line represents the parent of node $j+1$ in tree $T_i$.
Output
Output a single integer representing the answer.
Examples
Input 1
7
7 1 3 1 7 1
3 5 3 1 5 3Output 1
11Note 1
The valid subsets $S$ are $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}, \{1, 5\}, \{3, 4\}, \{1, 3, 5\}, \{1, 3, 4, 5\}$.
Additional Examples
The provided files contain $10^4$ test cases with $n=10$ in ex_tree1.in/out.
Constraints
For all data, $1 \le n \le 2 \times 10^5, 1 \le p_{i,j} \le n$.
Subtask #1 (10 points): $n \le 5\,000$.
Subtask #2 (20 points): The degree of every node in $T_1$ and $T_2$ is at most $2$.
Subtask #3 (30 points): The degree of every node in $T_1$ and $T_2$ is at most $3$.
Subtask #4 (40 points): No special properties.