题目描述

Pakenomy 公司由 $N$ 个房间和 $N-1$ 条走廊组成.我们为房间编号$1 \sim N$，走廊编号 $1 \sim N-1$。走廊 $i$ 将房间 $A_i$ 和房间 $B_i$ 双向连接。通过几条走廊，可以在任意两个房间之间移动。

Pakenomy 公司管理着很多怪物。一旦发生紧急情况，这些怪物就会侵入走廊。Iihachi 是负责镇压骚动的职员。但他想事先调查一下这些行为。

当 Iihachi 通过走廊 $e$ 时，体力会减少 $C_e$。当体力小于等于 $0$ ，就会“复苏”，体力会变成 $K$。

题目有 $Q$ 次询问，第 $i$ 个问题为：

• 当 Iihachi 初始以体力 $K$ 的状态，从房间 $S_i$ 通过走廊到房间 $T_i$ 的途中，最少“复苏”几次。

输入格式

第一行读入两个正整数 $N,K$。

接下来 $N-1$ 行，每行读入三个正整数 $A_i,B_i,C_i$。

接下来一行，读入一个正整数 $Q$。

接下来 $Q$ 行，每行读入两个正整数 $S_i,T_i$。

输出格式

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

数据范围

本题采用捆绑测试。

• Subtask 1(5 pts) 满足 $N=2,\ Q=1$。
• Subtask 2(18 pts) 满足 $N\ \leq\ 4000,\ Q\ \leq\ 4000$。
• Subtask 3(12 pts) 满足 $N\ \leq\ 4000$。
• Subtask 4(33 pts) 对于任意 $i（1\leq i\leq N-1）$，满足$A_i=i$ 及 $B_i=i+1$。
• Subtask 5(32 pts) 无附加条件。

对于 $100\%$ 的数据，保证

• 输入均为整数
• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ K\ \leq\ 10^9$
• $1\ \leq\ A_i,\ B_i\ \leq\ N\ (1\ \leq\ i\ \leq\ N-1)$
• 通过几条走廊，可以在任意两个房间之间移动
• $0\ \leq\ C_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N-1)$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ S_i,\ T_i\ \leq\ N\ (1\ \leq\ i\ \leq\ Q)$
• $S_i\ \neq\ T_i\ (1\ \leq\ i\ \leq\ Q)$

样例解释

对于样例一：

由房间 $3$ 至房间 $6$：

• 通过走廊 $2$，体力变为 $5-10=-5$。“复苏”，体力变为 $5$。
• 通过走廊 $1$，体力变为 $5-3=2$。
• 通过走廊 $5$，体力变为 $2-2=0$。“复苏”，体力变为 $5$。

由房间 $4$ 至房间 $7$：

• 通过走廊 $3$，体力变为 $5-3=2$。
• 通过走廊 $1$，体力变为 $2-3=-1$。“复苏”，体力变为 $5$。
• 通过走廊 $4$，体力变为 $5-1=4$。
• 通过走廊 $6$，体力变为 $4-1=3$。

由房间 $7$ 至房间 $6$：

• 通过走廊 $6$，体力变为 $5-1=4$。
• 通过走廊 $4$，体力变为 $4-1=3$。
• 通过走廊 $5$，体力变为 $3-2=1$。

对于样例二，每次经过走廊都会“复苏”。

@lihl 提供翻译。