【问题描述】

现有一个 N 个节点的有根树，根为1号节点，且每个节点有一个颜色。

现有若干询问，每个询问为一组颜色$(C_i,C_j)$, 问有多少点对$(a_i,a_j)$满足$a_i$的颜色是$C_i$, $a_j$的颜色是$C_j$且$a_j$是$a_i$的祖先。题目的询问还有一个有趣的性质，两种颜色中一定存在一种颜色其节点个数不超过$\sqrt n$.

【输入格式】

输入第一行包含一个正整数n, r，表示树的节点数和颜色数。

输入第二行至第 n 行中，每行包含1个正整数，表示第 i 号节点的父亲节点编号，由于1是根节点，所以只有 n-1 行。

输入第 n + 1 行包含 n 个正整数，表示节点的颜色。

接下来一行包含一个正整数 q , 表示询问数。

接下来的 q 行， 每行包含两个正整数，表示一组颜色的询问$(C_i,C_j)$。

本题需要大家设计在线的做法，每组询问的颜色标号（都需要）需要减去上一次的答案，第一次的询问为正常询问，不需要特殊处理。

【输出格式】

输出共 t 行，每行一个数表示所求的节点对的个数。

【输入输出样例 1】

track.in

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

track.out

2
1

【数据规模与约定】

对于 30% 的数据，$n \leq 1000$

对于另外 20% 的数据，满足询问$(C_i,C_j)$,中 $C_i$ 的节点数不超过$ \sqrt n $.

对于另外 20% 的数据，满足询问$(C_i,C_j)$,中 $C_J$的节点数不超过$\sqrt n$.

对于100% 的数据，$n,C_i,q \leq 10000$