题目描述

Klimi 正在准备国家考试。今天复习的主题是图论，更准确地说，是树。

在往年题目中，他遇到了这样一道题：

给定一棵有 N 个顶点的树，顶点编号为 1 到 N。每个顶点有一个颜色，颜色编号也在 1 到 N 之间，即顶点 i 的颜色为 C_i。

注意，对颜色没有额外限制：

• 某些颜色可能在整棵树中根本没有出现；
• 另一些颜色则可能出现很多次。

接下来有 Q 个询问。每个询问给出两个不同的整数 X 和 Y，要求你求出：

• 树中有多少条路径，
• 其两个端点的颜色都为 X，
• 并且路径上至少包含一个颜色为 Y 的顶点。

说明： 若两条路径所包含的顶点集合不同，则认为它们是不同的路径。

请你编写程序 colors.cpp 来回答所有询问。

输入格式

第一行输入整数 N。
第二行输入 N 个整数：C_1, C_2, ..., C_N。
接下来 N-1 行，每行输入两个整数，表示树的一条边。
接下来一行输入整数 Q。
接下来 Q 行，每行输入两个整数 X 和 Y，表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示满足条件的路径数量。

如果某个询问中涉及的某种颜色在树中根本没有出现，则该询问答案为 0。

数据范围

• 2 <= N, Q <= 80000
• 1 <= X, Y, C_i <= N

子任务

要获得某个子任务的分数，你的程序必须通过该子任务及之前所有子任务中的所有测试。

样例

输入

7
1 3 2 2 1 1 1
1 2
1 3
2 4
2 5
3 6
4 7
6
1 2
2 1
1 3
3 1
2 3
3 2

输出

5
1
5
0
1
0

样例解释

1. 1-6, 1-7, 5-6, 5-7, 6-7
2. 3-4
3. 1-5, 1-7, 5-6, 5-7, 6-7
4. 不存在这样的路径
5. 3-4
6. 不存在这样的路径