题目背景

某年秋季联赛提高组第一天第二题。

题目描述

小舟觉得晨跑特别有意思，干脆自己动手做了一款名为《校园晨跑》的养成小游戏，玩家每天按时上线完成打卡任务。

游戏的地图可以看作一棵包含 $n$ 个结点和 $n-1$ 条边的树：每条边连接两个结点，任意两个结点之间都存在路径互相可达，结点按 $1$ 到 $n$ 编号。

游戏里有 $m$ 位玩家，第 $i$ 位玩家的起点是 $s_i$，终点是 $t_i$。每天打卡任务开启时，所有玩家在第 $0$ 秒同时从各自起点出发，以每秒跑过一条边的速度，沿最短路径不停地奔向自己的终点，到达终点即完成当天的打卡。（地图是一棵树，因此每个人的行进路线唯一确定。）

为了统计游戏热度，小舟在每个结点上安排了一名观察员。结点 $j$ 的观察员只在第 $w_j$ 秒抬头看一眼：一位玩家能被这名观察员看到，当且仅当他在第 $w_j$ 秒恰好到达结点 $j$。小舟想知道，每名观察员各自能看到多少位玩家？

注意：玩家到达终点后就立即退出游戏，不能停在原地等待之后再被看到。也就是说，对于以结点 $j$ 为终点的玩家：若他在第 $w_j$ 秒之前就已到达，结点 $j$ 的观察员看不到他；若他恰好在第 $w_j$ 秒到达终点，观察员可以看到他。

输入格式

第一行两个整数 $n$ 和 $m$，其中 $n$ 表示树的结点数量（也是观察员的数量），$m$ 表示玩家数量。

接下来 $n-1$ 行，每行两个整数 $u$、$v$，表示结点 $u$ 与结点 $v$ 之间有一条边。

接下来一行 $n$ 个整数，第 $j$ 个整数为 $w_j$，表示结点 $j$ 的观察员抬头的时刻。

接下来 $m$ 行，每行两个整数 $s_i$、$t_i$，表示一位玩家的起点与终点。

对于所有数据，保证 $1\leq s_i,t_i\leq n$，$0\leq w_j\leq n$。

输出格式

输出一行 $n$ 个整数，第 $j$ 个整数表示结点 $j$ 的观察员能够看到的玩家数量。

样例

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

2 0 0 1 1 1

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

1 2 1 0 1

提示

样例 1 说明

对于 $1$ 号点，$w_i=0$，只有起点在 $1$ 号点的玩家才会被看到，因此玩家 $1$ 和玩家 $2$ 被看到，共 $2$ 人。

对于 $2$ 号点，第 $2$ 秒时没有玩家位于此结点，共 $0$ 人。

对于 $3$ 号点，第 $5$ 秒时没有玩家位于此结点，共 $0$ 人。

对于 $4$ 号点，玩家 $1$ 被看到，共 $1$ 人。

对于 $5$ 号点，玩家 $1$ 被看到，共 $1$ 人。

对于 $6$ 号点，玩家 $3$ 被看到，共 $1$ 人。

子任务

各测试点的数据规模及特点如下表所示。（数据范围个位上的数字可以帮助判断数据类型。）

提示

评测环境中调用栈空间不单独设限，但递归层数过深（例如树退化为链时）仍可能耗尽栈空间导致崩溃，请注意程序所需的栈空间，调用栈占用的空间会计入总内存。