{"raw_statement":[{"iden":"statement","content":"JOI 王国是一个由 $N$ 个岛屿组成的岛国，编号从 $1$ 到 $N$。这些岛屿通过 $N - 1$ 座桥相连，编号从 $1$ 到 $N - 1$。桥 $i\\ (1 \\leq i \\leq N - 1)$ 双向连接岛屿 $A_i$ 和岛屿 $B_i$。可以通过若干座桥从任意一个岛屿到达另一个岛屿。在 JOI 王国，有 $M$ 个观光景点，编号从 $1$ 到 $M$。观光景点 $j\\ (1 \\leq j \\leq M)$ 位于岛屿 $C_j$。有 $Q$ 位旅行者，他们计划参观 JOI 王国的观光景点。旅行者编号从 $1$ 到 $Q$。每位旅行者按以下方式旅行。\n\n1. 旅行者选择一个岛屿 $x\\ (1 \\leq x \\leq N)$。乘坐飞机，旅行者到达岛屿 $x$。\n2. 旅行者进行若干次以下动作。动作的顺序和种类是任意的。\n\n    - 旅行者选择当前岛屿上的一个观光景点，并参观。\n    - 旅行者通过桥梁移动到另一个岛屿。\n\n3. 乘坐飞机，旅行者离开 JOI 王国。旅行者 $k\\ (1 \\leq k \\leq Q)$ 想要参观所有的观光景点 $L_k, L_k+1, \\ldots, R_k$。然而，由于预算有限，旅行者 $k$ 希望最小化至少访问一次的岛屿数量。"},{"iden":"input","content":"从标准输入读取以下数据。\n\n> $N\\ M\\ Q$\n\n> \n\n> $A_1\\ B_1$\n\n> \n\n> $A_2\\ B_2$\n\n> \n\n> $\\vdots$\n\n> \n\n> $A_{N-1}\\ B_{N-1}$\n\n> \n\n> $C_1\\ C_2\\ \\cdots\\ C_M$\n\n> \n\n> $L_1\\ R_1$\n\n> \n\n> $L_2\\ R_2$\n\n> \n\n> $\\vdots$\n\n> \n\n> $L_Q\\ R_Q$"},{"iden":"output","content":"向标准输出写入 $Q$ 行。输出的第 $k$ 行 $(1 \\leq k \\leq Q)$ 应包含旅行者 $k$ 至少访问一次的岛屿的最小可能数量。"},{"iden":"note","content":"**【样例解释 #1】**\n\n旅行者 1 按以下方式旅行，并参观所有的观光景点 1, 2, 3。\n1. 旅行者 1 到达岛屿 2。\n2. 旅行者 1 参观岛屿 2 上的观光景点 1。\n3. 旅行者 1 通过桥梁 1 从岛屿 2 移动到岛屿 1。\n4. 旅行者 1 通过桥梁 2 从岛屿 1 移动到岛屿 3。\n5. 旅行者 1 参观岛屿 3 上的观光景点 2。\n6. 旅行者 1 通过桥梁 5 从岛屿 3 移动到岛屿 6。\n7. 旅行者 1 参观岛屿 6 上的观光景点 3。\n8. 旅行者 1 从岛屿 6 出发，离开 JOI 王国。\n\n岛屿 1, 2, 3, 6 是旅行者 1 至少访问一次的四个岛屿。如果旅行者 1 至少访问一次的岛屿数量小于或等于 3，则不可能参观所有的观光景点 1, 2, 3。因此，第一行输出 4。旅行者 2 按以下方式旅行，并参观所有的观光景点 4, 5, 6。\n1. 旅行者 2 到达岛屿 3。\n2. 旅行者 2 通过桥梁 6 从岛屿 3 移动到岛屿 7。\n3. 旅行者 2 参观岛屿 7 上的观光景点 6。\n4. 旅行者 2 通过桥梁 6 从岛屿 7 移动到岛屿 3。\n5. 旅行者 2 通过桥梁 2 从岛屿 3 移动到岛屿 1。\n6. 旅行者 2 通过桥梁 1 从岛屿 1 移动到岛屿 2。\n7. 旅行者 2 通过桥梁 3 从岛屿 2 移动到岛屿 4。\n8. 旅行者 2 参观岛屿 4 上的观光景点 4。\n9. 旅行者 2 通过桥梁 3 从岛屿 4 移动到岛屿 2。\n10. 旅行者 2 通过桥梁 4 从岛屿 2 移动到岛屿 5。\n11. 旅行者 2 参观岛屿 5 上的观光景点 5。\n12. 旅行者 2 从岛屿 5 出发，离开 JOI 王国。\n\n岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。此样例输入满足子任务 1, 2, 4, 5, 6 的约束。\n\n岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。\n\n此样例输入满足子任务 1, 2, 4, 5, 6 的约束。\n\n**【样例解释 #2】**\n\n此样例输入满足子任务 1, 2, 3, 6 的约束。\n\n**【样例解释 #3】**\n\n此样例输入满足子任务 1, 2, 6 的约束。\n\n**【数据范围】**\n\n- $1 \\leq N \\leq 100 000$。\n- $1 \\leq M \\leq 100 000$。\n- $1 \\leq Q \\leq 100 000$。\n- $1 \\leq A_i \\leq N\\ (1 \\leq i \\leq N - 1)$。\n- $1 \\leq B_i \\leq N\\ (1 \\leq i \\leq N - 1)$。\n- 可以通过若干座桥从任意一个岛屿到达另一个岛屿。\n- $1 \\leq C_j \\leq N\\ (1 \\leq j \\leq M)$。\n- $1 \\leq L_k \\leq R_k \\leq M\\ (1 \\leq k \\leq Q)$。\n- 给定的值都是整数。\n\n**【子任务】**\n\n1. (5 分) $N \\leq 300, M \\leq 300, Q \\leq 300$。\n2. (5 分) $N \\leq 2 000, M \\leq 2 000, Q \\leq 2 000$。\n3. (7 分) $A_i = i, B_i = i + 1\\ (1 \\leq i \\leq N - 1)$。\n4. (18 分) $L_1 = 1, R_{k} + 1 = L_{k+1}\\ (1 \\leq k \\leq Q - 1), R_Q = M$。\n5. (24 分) $A_i = \\lfloor\\frac{i+1}2\\rfloor, B_i = i + 1\\ (1 \\leq i \\leq N-1)$。这里，$\\lfloor x\\rfloor$ 是不超过 x 的最大整数。\n6. (41 分) 无额外约束。\n\n题面翻译由 ChatGPT-4o 提供。"}],"translated_statement":null,"sample_group":[["7 6 2\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n2 3 6 4 5 7\n1 3\n4 6","4\n6"],["8 8 9\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 6 4 3 5 2 4 7\n3 5\n4 6\n6 8\n1 4\n2 3\n6 8\n5 5\n2 8\n1 2","3\n4\n6\n6\n3\n6\n1\n6\n3"],["10 7 9\n6 5\n3 6\n9 3\n8 3\n7 8\n7 1\n2 5\n7 10\n8 4\n9 4 10 1 10 7 6\n4 4\n1 3\n1 3\n6 7\n3 6\n3 3\n1 5\n2 5\n1 2","1\n6\n6\n4\n3\n1\n7\n5\n4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}