[AHOI2022] 钥匙

有 $n$ 座城市，编号为 $1, 2, \ldots, n$。这些城市由 $n - 1$ 条无向道路相连，每条无向道路连接两座城市，保证任意两个城市连通。即这 $n$ 座城市构成一棵树。 每座城市都有一件宝物。宝物分为两种：钥匙和宝箱。在一座城市里，要么有一把钥匙，要么有一个宝箱。钥匙和宝箱有不同的颜色，颜色为 $i$ 的钥匙只能打开颜色为 $i$ 的宝箱，打开宝箱后可以获得一枚金币，同时这把钥匙会损坏。 **由于某种特殊的原因，同一种的钥匙最多只有 $\bm{5}$ 把（同一种颜色的宝箱数量不限）。** 现在小 R 规划了 $m$ 次旅行，第 $i$ 次旅行的起点为 $s_i$，终点为 $e_i$。小 R 从 $s_i$ 沿最短路径走到 $e_i$。当他走到一座有钥匙的城市时，他可以将钥匙放入背包。当他走到一座有宝箱的城市时，如果他有相应颜色的钥匙，那么他就会打开这个宝箱并获得一个金币；如果他没有相应颜色的钥匙，那么他什么都不做（宝箱不能带走）。问每次旅行能获得多少枚金币。 **注意：旅行相互独立，即一次旅行完之后所有的钥匙和宝箱都会恢复到初始状态。** ## Input 第一行两个正整数 $n, m$，表示城市数量和旅行数量。 接下来 $n$ 行，每行两个正整数 $t_i, c_i$，$t_i=1$ 表示第 $i$ 个城市里有一把钥匙，$t_i=2$ 表示有一个宝箱。$c_i$ 表示第 $i$ 座城市里钥匙或宝箱的颜色。数据保证每种颜色的钥匙都不超过 $5$ 把。 接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示有一条连接 $u_i$ 和 $v_i$ 的无向道路。 接下来 $m$ 行，每行两个正整数 $s_i, e_i$ 表示一次旅行的起点和终点。 ## Output 输出 $m$ 行，每行一个整数，表示第 $i$ 次旅行能获得的金币数量。 [samples] ## Note **【样例 \#4】** 见附件中的 `keys/keys4.in` 与 `keys/keys4.ans`。 该组样例满足 $n, m \le {10}^5$ 和特殊性质 A。 **【数据范围】** 对于 $100 \%$ 的数据，$1 \le n \le 5 \times {10}^5$，$1 \le m \le {10}^6$，$1 \le t_i \le 2$，$1 \le c_i, u_i, v_i, s_i, e_i \le n$，每种颜色的钥匙都不超过 $5$ 把。 | 测试点编号 | $n \le$ | $m \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1$ | $100$ | $100$ | 无 | | $2 \sim 3$ | $5000$ | $5000$ | 无 | | $4 \sim 5$ | ${10}^5$ | ${10}^5$ | 无 | | $6 \sim 8$ | $5 \times {10}^5$ | ${10}^6$ | A | | $9 \sim 10$ | $5 \times {10}^5$ | ${10}^6$ | 无 | 特殊性质 A：对于每种出现过的颜色，恰有一把钥匙和一个宝箱对应该颜色。 **【提示】** 输入输出数据较大，请使用较为快速的输入输出方式。