在 Byteopolis 有 $n$ 个公交车站，编号为 $1$ 到 $n$，由 $n-1$ 条双向道路连接，使得从任意一个车站出发都能通过道路到达其他任何车站。换句话说，公交车站及其连接的道路构成了一棵树。

Byteopolis 有 $m$ 条公交线路。第 $i$ 条线路的公交车在车站 $c_i$ 和 $d_i$ 之间的最短路径上往返行驶。乘客可以在其路线上的任何车站（包括终点站）上下车。这些线路的规划保证了乘客仅使用公交车即可从任意车站到达其他任何车站，而无需通过道路行走任何距离。

设 $f(i, j)$（其中 $1 \le i, j \le n$）表示从车站 $i$ 到车站 $j$ 所需的最少公交线路数。特别地，对于每个 $i$，有 $f(i, i) = 0$，且对于所有点对 $(i, j)$，有 $f(i, j) = f(j, i)$。你的任务是计算对于每个车站 $i$，$\sum_{j=1}^n f(i, j)$ 的值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示 Byteopolis 的公交车站数量。

接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示公交车站 $a_i$ 和 $b_i$ 之间有一条道路相连。保证这些道路构成一棵合法的树。

随后一行包含一个整数 $m$ ($1 \le m \le 200\,000$)，表示公交线路的数量。

接下来的 $m$ 行，每行包含两个整数 $c_i$ 和 $d_i$ ($1 \le c_i, d_i \le n; c_i \neq d_i$)，表示有一条在车站 $c_i$ 和 $d_i$ 之间往返的公交线路。保证仅使用这些公交车即可从任意车站到达其他任何车站。

输出格式

输出一行，包含 $n$ 个整数，其中第 $i$ 个整数应等于 $\sum_{j=1}^n f(i, j)$。

样例

输入 1

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

输出 1

6 9 9 10 7 7

说明

样例测试中车站和道路的布局如下：

如果我们想从车站 $2$ 到达车站 $4$，我们首先需要乘坐第二条公交线路（在车站 $2$ 和 $3$ 之间运行）并在车站 $1$ 下车。接下来，我们应该乘坐第一条公交线路（在车站 $6$ 和 $1$ 之间运行）并在车站 $5$ 下车。最后，我们应该使用最后一条公交线路到达目的地。仅使用两条线路无法在这些车站之间移动，因此 $f(2, 4) = 3$。

样例测试中所有的 $f(i, j)$ 值如下表所示，其中第 $i$ 行第 $j$ 列的单元格包含 $f(i, j)$ 的值。程序输出的数字应等于各行数值之和：