Farmer John 利用业余时间创建了一个名为 MooTube 的新视频分享服务。在 MooTube 上，他的奶牛可以录制、分享和发现许多有趣的视频。奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 5000$），编号为 $1 \ldots N$。然而，FJ 还不知道怎样帮助奶牛找到可能喜欢的新视频。

FJ 希望为每个 MooTube 视频建立一个“推荐视频”列表，从而向奶牛推荐与已经观看的视频最相关的视频。

FJ 设计了一个“相关度”指标，顾名思义，它衡量两个视频之间的相关程度。他选取 $N-1$ 对视频，手动计算每对的相关度。随后，他将视频表示为一个网络，每个视频是一个节点，手动考虑的 $N-1$ 对视频之间连有边。他选取的 $N-1$ 对保证任意两个视频之间恰有一条连接路径。FJ 将任意一对视频的相关度定义为该路径上所有连接的最小相关度。

Farmer John 希望选择一个 $K$，使任意 MooTube 视频旁都会推荐所有与它的相关度至少为 $K$ 的其他视频。不过，FJ 担心推荐太多视频会让奶牛分心，影响产奶！因此，他想谨慎地设置合适的 $K$。请帮助 Farmer John 回答若干关于特定 $K$ 值下推荐视频的问题。

输入格式

第一行包含 $N$ 和 $Q$（$1 \leq Q \leq 5000$）。

接下来 $N-1$ 行各描述 FJ 手动比较的一对视频。每行包含三个整数 $p_i$、$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$），表示视频 $p_i$ 和 $q_i$ 之间的连接相关度为 $r_i$。

接下来 $Q$ 行描述 Farmer John 的 $Q$ 个问题。每行包含两个整数 $k_i$ 和 $v_i$（$1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问：当 $K = k_i$ 时，观看视频 $v_i$ 的奶牛会收到多少个推荐视频。

输出格式

输出 $Q$ 行，第 $i$ 行输出 FJ 的第 $i$ 个问题的答案。

样例

输入格式 1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

输出格式 1

3
0
2

说明

Farmer John 发现视频 1 和 2 的相关度为 3，视频 2 和 3 的相关度为 2，视频 2 和 4 的相关度为 4。因此，视频 1 和 3 的相关度为 $min(3, 2) = 2$，视频 1 和 4 的相关度为 $min(3, 4) = 3$，视频 3 和 4 的相关度为 $min(2, 4) = 2$。

Farmer John 想知道 $K=1$ 时从视频 2、$K=3$ 时从视频 1，以及 $K=4$ 时从视频 1 会推荐多少个视频。$K=1$ 时，视频 2 会推荐视频 1、3 和 4。$K=4$ 时，视频 1 不推荐任何视频。而 $K=3$ 时，视频 1 会推荐视频 2 和 4。

题目作者：Jay Leeds