题目背景

本题与 银组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 10^5$），为了方便将其编号为 $1 \ldots N$。然而，FJ 无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

FJ 希望为每个 MooTube 视频创建一个“推荐视频”列表。这样，奶牛将被推荐与他们已经观看过的视频最相关的视频。

FJ 设计了一个“相关性”度量标准，顾名思义，它确定了两个视频相互之间的相关值。FJ 将他的视频建成一棵树（其中每个节点代表一条视频），并且计算了所有 $N-1$ 对相邻视频的相关值。这样任意视频都可以通过一条连通路径到达任意其他视频。FJ 决定将任意一对视频的相关值定义为沿此路径的任何连接的最小相关值。

Farmer John 想要选择一个 $K$ 值，以便在任何给定的 MooTube 视频旁边，推荐所有其他与该视频相关值至少为 $K$ 的视频。然而，FJ 担心会向他的奶牛推荐太多的视频，这可能会分散他们对产奶的注意力！因此，他想设定适当的 $K$ 值。Farmer John 希望得到您的帮助，回答有关 $K$ 值的推荐视频的一些问题。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 10^5$）。

接下来的 $N-1$ 行描述了 FJ 手动比较的一对视频。 每行包括三个整数 $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关值为 $r_i$。

接下来的 $Q$ 行描述了 Farmer John 的 $Q$ 个问题。每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

输出格式

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

数据范围与约定

他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 10^5$），为了方便将其编号为 $1 \ldots N$。

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 10^5$）。

每行包括三个整数 $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关值为 $r_i$。

每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

可见测试数据

输入数据 1

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

输出数据 1

3
0
2

输入数据 2

2 2
1 2 380423270
22746887 1
315008309 2

输出数据 2

1
1

输入数据 3

3 3
1 2 88778552
2 3 544938918
87835752 2
704043783 3
136493302 2

输出数据 3

2
0
1