### 问题描述

一个机器人工厂有编号为 $1$ 到 $n$ 的 $n$ 个机器人。这些机器人组成了一个层级结构，每个机器人最多只有一个直接上级，每个机器人都有一个型号，这些型号不一定唯一。

如果编号为 $a$ 的机器人是编号为 $b$ 的机器人的直接上级，则称编号为 $a$ 的机器人是编号为 $b$ 的 $1$ 级上级。

如果编号为 $a$ 的机器人是编号为 $b$ 的 $1$ 级上级的 $(k-1)$ 级上级，则称编号为 $a$ 的机器人是编号为 $b$ 的 $k$ 级上级（$k > 1$）。

> 编号为 $1$ 的机器人是所有机器人的上级。

工厂中的层级关系不会形成循环。换句话说，没有一个机器人是它自己的直接或间接上级（即，对于某个$x$，$x > 0$，没有一个机器人是其自身的 $x$ 级上级）。

如果编号为 $a$ 的机器人是编号为 $b$ 的 $k$ 级上级，则称编号为 $b$ 的机器人是编号为 $a$ 的 $k$ 级下属。

工厂管理者希望了解每个机器人的下属情况，包括下属的数量以及各个下属的型号。他们提供了一个列表，包含 $m$ 对数字 $u_i$ 和 $k_i$。请帮助他们确定对于每对 $u_i$ 和 $k_i$，编号为 $u_i$ 的机器人的 $k_i$ 级下属中有多少个不同的型号。

输入格式

输入的第一行将包含一个整数 $n$（$1 \le n \le 10^5$），表示机器人的数量。

接下来的 $n - 1$ 行每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \ne b$），表示编号为 $b$ 的机器人的直接上级是编号为 $a$ 的机器人。

接下来的一行包含一个整数 $m$（$1 \le m \le 10^5$），表示询问的数量。

接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $k_i$（$1 \le u_i \le n$，$1 \le k_i \le n - 1$），询问编号为 $u_i$ 的机器人的 $k_i$ 级下属中有多少个不同的型号。

最后一行包含 $n$ 个由小写字母组成的字符串，以空格分隔，表示每个机器人的型号。字符串长度不超过 $10$。

输出格式

对于每个询问，输出一行包含一个整数，表示编号为 $u_i$ 的机器人的 $k_i$ 级下属中有多少个不同的型号。

输入样例

6
1 2
1 3
1 6
2 4
3 5
5
1 1
1 2
1 3
3 1
6 1
qwqwq lanqiao lanqiao hello world ovo

输出样例

2
2
0
1
0

说明

• 在第一个询问中，编号为 $1$ 的机器人的 $1$ 级下属分别为 $(\mathrm{qwq}, \mathrm{lanqiao}, \mathrm{lanqiao})$，共 $2$ 种不同型号。
• 在第二个询问中，编号为 $1$ 的机器人的 $2$ 级下属分别为 $(\mathrm{hello}, \mathrm{world})$，共 $2$ 种不同型号。
• 在第三个询问中，编号为 $1$ 的机器人没有 $3$ 级下属，所以询问的结果为 $0$。
• $\cdots$