{"raw_statement":[{"iden":"background","content":"生活在题面里的他们，是一群怪异的少年。\n\n对城市中修建道路需满足的基本物理限制熟视无睹，沉迷于十万个城市、百万条道路上的各种结构。\n\n明明知道真正需要的数字庞大到无法计算，却偏要关心它模一个奇怪素数之后得到的结果。\n\n如此智力超群的他们，却总是在自己提出的诡异的问题下败下阵来，把它们一股脑地丢给你们来做。\n\n如今，他们长大了。他们学习到更普适的理论，习惯了更抽象的符号，不必再思考如此古怪的问题。但他们不曾料到，你们却以这些 “无用” 的问题为驱动，于计算机学科体系的一隅，开垦出了一片独属于 OI 的新天地。\n\n有一天，他们各自回忆起了少年时期提出的问题。"},{"iden":"statement","content":"少年时，他们提出了 $n$ 个问题，从 $1$ 到 $n$ 编号。一个问题总由一个更基础的问题衍生而来，因此问题之间构成了一个树形的结构：$1$ 号问题是最基本的问题，也就是树的根节点，而其他问题都由其父亲节点对应的问题衍生而来。如果两个问题在树上相邻，则称这两个问题**彼此相关**。\n\n少年时期的他们一共做了 $m$ 次研究，第 $i$ 次的研究从提出较为基本的问题 $s_i$ 开始，将它不断地修改、推广，最终提出问题 $t_i$。这些研究满足 $s_i \\ne t_i$ 且 **$\\bm{s_i}$ 必定是 $\\bm{t_i}$ 的祖先**。即使研究的问题完全相同，从不同的角度研究会有不同的结果，因此**可能存在 $\\bm{i \\ne j, (s_i, t_i) = (s_j, t_j)}$ 的情形**。\n\n现在，他们正一轮轮地回忆着少年时提出的问题。在他们每一轮对问题的回忆中，他们首先回忆到 $n$ 个问题中的任意一个。接下来，如果存在与当前回忆到的问题**彼此相关且在这轮回忆中没有被回忆到**的问题，那么他们可以将思绪从当前问题上切换到这些问题中的**任意一个**，并回忆到这个新的问题。他们可以不断地切换思绪，也可以在回忆到任何一个问题之后结束回忆。**每一轮回忆是独立的，也就是说一个问题可以被多轮回忆回忆起。**\n\n如果在某一轮回忆中，他们**同时**回忆到了问题 $s_i$ 和问题 $t_i$，则称第 $i$ 次研究**被想起**。\n\n为了更好地理解上述概念，考察以下例子：$n = 5$，问题 $1$ 与问题 $2, 3$ 相关，问题 $3$ 与问题 $4, 5$ 相关。一轮可能的回忆是：从问题 $2$ 开始回忆，切换思绪到问题 $1$，再切换到问题 $3$，最终切换到问题 $5$ 并结束回忆。如果 $m = 4$，$(s_1, t_1) = (1, 2), (s_2, t_2) = (1, 4), (s_3, t_3) = (s_4, t_4) = (3, 5)$，那么这轮回忆会让第 $1$ 次、第 $3$ 次和第 $4$ 次研究被想起，而第 $2$ 次研究不会被想起。\n\n他们问你们的最后一个问题是：**如果每轮回忆的起点以及思绪的切换可以任意选择，最少需要多少轮回忆才能使所有的研究都被想起。**"},{"iden":"input","content":"**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示数据组数。\n\n对于每组测试数据，第一行包含两个正整数 $n, m$，分别表示问题的个数和研究的个数。\n\n接下来 $n - 1$ 行每行包含两个正整数 $u_i, v_i$，表示问题 $u_i$ 与问题 $v_i$ 相关。\n\n接下来 $m$ 行每行包含两个正整数 $s_i, t_i$，描述一次研究。"},{"iden":"output","content":"对于每组测试数据输出一行一个正整数，表示他们**最少**需要回忆的轮数使得 $m$ 次研究均被想起。"},{"iden":"note","content":"**【样例解释 \\#1】**\n\n样例中的第一组数据与题目描述所给的例子相同。一种可能的回忆方案为：\n\n- 第一轮回忆中，从问题 $2$ 开始，依次切换思绪到问题 $1, 3, 5$。此时第 $1, 3, 4$ 次研究被想起，但第 $2, 5$ 次没有。\n- 第二轮回忆中，从问题 $4$ 开始，依次切换思绪到问题 $3, 1$。此时第 $2, 5$ 次研究被想起。\n\n第二组数据符合特性 A 的要求。一种可能的回忆方案为：第一次回忆依次回忆到 $2, 1, 3, 5, 6$，第二次回忆依次回忆到 $8, 7, 9, 10$。\n\n**【样例 \\#2】**\n\n见附件中的 `memory/memory2.in` 与 `memory/memory2.ans`。\n\n这组数据满足了测试点 $1 \\sim 4$ 的条件。\n\n**【样例 \\#3】**\n\n见附件中的 `memory/memory3.in` 与 `memory/memory3.ans`。\n\n这组样例满足了特性 A 的条件。且除了后 $3$ 组数据外，其余样例均满足 $n, m \\le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \\le 30$。你也可以用这组样例完成对较小规模数据的测试。\n\n**【样例 \\#4】**\n\n见附件中的 `memory/memory4.in` 与 `memory/memory4.ans`。\n\n这组样例满足了测试点 $24 \\sim 25$ 的条件。同样例 \\#3，本样例满足：除了后 $3$ 组数据外，其余样例均满足 $n, m \\le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \\le 30$。你也可以用这组样例完成对较小规模数据的测试。\n\n**【样例 \\#5】**\n\n见附件中的 `memory/memory5.in` 与 `memory/memory5.ans`。\n\n这组样例满足了特性 B 的条件。\n\n**【样例 \\#6】**\n\n见附件中的 `memory/memory6.in` 与 `memory/memory6.ans`。\n\n这组样例满足了特性 C 的条件。\n\n**【评分方式】**\n\n对于每一组测试点，如果你的输出格式正确，且每一组数据输出的答案正确，那么你会获得 $4$ 分。\n\n否则，如果你的输出格式正确，且对于每一组数据，你输出的答案**与正确答案相等或者比正确答案大 $\\bm{1}$**，那么你将在此测试点上获得 $3$ 分。\n\n**【数据范围】**\n\n本题共 $25$ 个测试点。对于所有的测试点，$1 \\le n, m \\le 2 \\times {10}^5$，$1 \\le \\sum n, \\sum m \\le\n5 \\times {10}^5$，$1 \\le u_i, v_i, s_i, t_i \\le n$，$s_i \\ne t_i$。保证输入的 $(u_i, v_i)$ 构成一棵树，$s_i$ 在以 $1$ 为根的树上是 $t_i$ 的祖先。\n\n| 测试点 | 规模限制 | 特殊性质 |\n|:-:|:-:|:-:|\n| $1 \\sim 4$ | $T \\le 3000$，$n \\le 50$，$m \\le 15$ 且最多有 $5$ 组数据满足 $m \\ge 10$ | 无 |\n| $5 \\sim 6$ | $n, m \\le 100$，$\\sum n^3, \\sum m^3 \\le 3 \\times {10}^7$ | A |\n| $7$ | $n, m \\le 100$，$\\sum n^3, \\sum m^3 \\le 3 \\times {10}^7$ | B |\n| $8$ | $n, m \\le 100$，$\\sum n^3, \\sum m^3 \\le 3 \\times {10}^7$ | C |\n| $9$ | $n, m \\le 100$，$\\sum n^3, \\sum m^3 \\le 3 \\times {10}^7$ | 无 |\n| $10 \\sim 11$ | $n, m \\le 1000$，$\\sum n^2, \\sum m^2 \\le 3 \\times {10}^7$ | A |\n| $12$ | $n, m \\le 1000$，$\\sum n^2, \\sum m^2 \\le 3 \\times {10}^7$ | B |\n| $13$ | $n, m \\le 1000$，$\\sum n^2, \\sum m^2 \\le 3 \\times {10}^7$ | C |\n| $14 \\sim 16$ | $n, m \\le 1000$，$\\sum n^2, \\sum m^2 \\le 3 \\times {10}^7$ | 无 |\n| $17 \\sim 18$ | $n, m \\le 2 \\times {10}^5$，$\\sum n, \\sum m \\le 5 \\times {10}^5$ | B |\n| $19 \\sim 20$ | $n, m \\le 2 \\times {10}^5$，$\\sum n, \\sum m \\le 5 \\times {10}^5$ | C |\n| $21 \\sim 23$ | $n, m \\le 2 \\times {10}^5$，$\\sum n, \\sum m \\le 5 \\times {10}^5$ | A |\n| $24 \\sim 25$ | $n, m \\le 2 \\times {10}^5$，$\\sum n, \\sum m \\le 5 \\times {10}^5$ | 无 |\n\n特殊性质 A：保证 $n$ 为偶数，且树的结构为：对于任意正整数 $1 \\le i \\le \\lfloor \\frac{n}{2} \\rfloor$，$2 i$ 的父亲为 $2 i - 1$；若 $i \\ge 2$，则 $2 i - 1$ 的父亲为 $2 i - 3$。  \n特殊性质 B：保证对于所有的正整数 $1 \\le i \\le m$，$s_i$ 为 $t_i$ 的父亲。  \n特殊性质 C：保证对于所有的正整数 $1 \\le i \\le m$，$s_i = 1$。\n\n请注意，**测试点的难度与编号并没有直接关系**。\n\n**【提示】**\n\n请注意，为了取得部分分，你必须保证输出格式正确，即：输出恰好有 $m$ 行，且每行是一个正整数。\n\n此外，如果某组测试数据中你输出的结果比答案小 $1$ 而不是大 $1$，那么你**不能**在该测试点获得 $3$ 分。\n\n本题部分测试点读入量较大。为了优化程序的总运行时间，我们建议你采用较为快速的读入方式。"}],"translated_statement":null,"sample_group":[["2\n5 5\n1 2\n3 1\n3 4\n5 3\n1 2\n1 4\n3 5\n3 5\n3 4\n10 5\n1 2\n3 1\n3 4\n5 3\n6 5\n7 8\n5 7\n7 9\n9 10\n1 2\n3 5\n5 6\n7 8\n9 10\n","2\n2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}