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