给定一棵顶点带有颜色的树，对于每一条边，求有多少对颜色相同的顶点，使得该边位于它们之间的路径上。注意，由于这是一棵树，任意一对节点之间有且仅有一条路径。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树中节点的数量。节点编号从 $1$ 到 $n$。
接下来的 $n$ 行，每行包含一个整数 $c$ ($1 \le c \le n$)，依次表示各节点的颜色。
接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示连接节点 $a$ 和节点 $b$ 的一条无向边。
输出格式
输出 $n-1$ 行。每行输出一个整数，表示颜色相同的顶点对中，路径经过该边的数量。请按照输入中边的顺序输出这些答案。
样例
输入 1
6 3 1 2 1 2 2 2 6 4 5 1 4 3 4 1 2
输出 1
2 2 3 2 3
输入 2
4 2 2 2 2 3 4 2 4 1 2
输出 2
3 4 3