P8341 [AHOI2022] Memories

Living inside the problem statement, they are a group of strange teenagers. They ignore the basic physical limits required for building roads in a city, and are obsessed with all kinds of structures over hundreds of thousands of cities and millions of roads. They clearly know that the true number they need is so huge that it cannot be computed, yet they still insist on caring about its value modulo some strange prime. Although they are so intelligent, they always lose to the weird questions they提出 themselves, and throw all of them to you to solve. Now, they have grown up. They have learned more general theories and got used to more abstract symbols, so they no longer need to think about such odd problems. But they never expected that you, driven by these “useless” problems, would open up a new world belonging only to OI in a corner of the computer science system. One day, they each recalled the problems they proposed in their teenage years.

When they were young, they proposed $n$ problems, numbered from $1$ to $n$. Each problem is derived from a more basic problem, so the problems form a tree structure: problem $1$ is the most basic one, i.e. the root of the tree, and every other problem is derived from the problem corresponding to its parent node. If two problems are adjacent on the tree, then these two problems are called **related to each other**. In their teenage years, they conducted $m$ studies. The $i$-th study started from a more basic problem $s_i$, continuously modified and generalized it, and finally proposed problem $t_i$. These studies satisfy $s_i \ne t_i$ and **$\bm{s_i}$ must be an ancestor of $\bm{t_i}$**. Even if the studied problems are exactly the same, studying them from different angles may produce different results, so **it is possible that $\bm{i \ne j, (s_i, t_i) = (s_j, t_j)}$**. Now they are recalling the problems they proposed back then, round by round. In each round of recalling, they first recall any one of the $n$ problems. Next, if there exists a problem that is **related to the currently recalled problem and has not been recalled in this round**, then they may switch their thoughts from the current problem to **any one** of these problems, and recall this new problem. They may keep switching thoughts, and they may also end the recalling after recalling any problem. **Each round of recalling is independent, meaning a problem may be recalled in multiple rounds.** If in some round of recalling they recall **both** problem $s_i$ and problem $t_i$, then the $i$-th study is said to be **remembered**. To better understand the above concepts, consider the following example: $n = 5$, problem $1$ is related to problems $2, 3$, and problem $3$ is related to problems $4, 5$. One possible round of recalling is: start from problem $2$, switch to problem $1$, then switch to problem $3$, and finally switch to problem $5$ and end. If $m = 4$, $(s_1, t_1) = (1, 2), (s_2, t_2) = (1, 4), (s_3, t_3) = (s_4, t_4) = (3, 5)$, then this round of recalling will make the $1$-st, $3$-rd, and $4$-th studies be remembered, while the $2$-nd study will not be remembered. Their final question to you is: **if the starting point of each round of recalling and the switches of thoughts can be chosen arbitrarily, what is the minimum number of rounds of recalling needed so that all studies are remembered.**

**This problem contains multiple test cases.** The first line of input contains a positive integer $T$, representing the number of test cases. For each test case, the first line contains two positive integers $n, m$, representing the number of problems and the number of studies. The next $n - 1$ lines each contain two positive integers $u_i, v_i$, indicating that problem $u_i$ is related to problem $v_i$. The next $m$ lines each contain two positive integers $s_i, t_i$, describing one study.

For each test case, output one line with one positive integer, representing the **minimum** number of rounds of recalling they need so that all $m$ studies are remembered.

**【Sample Explanation \#1】** The first test case in the sample is the same as the example given in the statement. One possible plan is: - In the first round, start from problem $2$, then switch thoughts to problems $1, 3, 5$ in order. At this time, the $1$-st, $3$-rd, and $4$-th studies are remembered, but the $2$-nd and $5$-th are not. - In the second round, start from problem $4$, then switch thoughts to problems $3, 1$ in order. At this time, the $2$-nd and $5$-th studies are remembered. The second test case satisfies the requirement of property A. One possible plan is: in the first round, recall $2, 1, 3, 5, 6$ in order, and in the second round, recall $8, 7, 9, 10$ in order. **【Sample \#2】** See the attached files `memory/memory2.in` and `memory/memory2.ans`. This test case satisfies the conditions of test points $1 \sim 4$. **【Sample \#3】** See the attached files `memory/memory3.in` and `memory/memory3.ans`. This sample satisfies property A. Also, except for the last $3$ test cases, all the other samples satisfy $n, m \le 1000$. Except for the last $30$ test cases, all the other samples satisfy $n, m \le 30$. You can also use this sample to test on smaller-scale data. **【Sample \#4】** See the attached files `memory/memory4.in` and `memory/memory4.ans`. This sample satisfies the conditions of test points $24 \sim 25$. Same as sample \#3, it satisfies: except for the last $3$ test cases, all the other samples satisfy $n, m \le 1000$. Except for the last $30$ test cases, all the other samples satisfy $n, m \le 30$. You can also use this sample to test on smaller-scale data. **【Sample \#5】** See the attached files `memory/memory5.in` and `memory/memory5.ans`. This sample satisfies property B. **【Sample \#6】** See the attached files `memory/memory6.in` and `memory/memory6.ans`. This sample satisfies property C. **【Scoring】** For each test point, if your output format is correct and the answers for every test case are correct, then you will get $4$ points. Otherwise, if your output format is correct and for every test case, the answer you output is **equal to the correct answer or larger than the correct answer by $\bm{1}$**, then you will get $3$ points on this test point. **【Constraints】** This problem has $25$ test points. For all test points, $1 \le n, m \le 2 \times {10}^5$, $1 \le \sum n, \sum m \le 5 \times {10}^5$, $1 \le u_i, v_i, s_i, t_i \le n$, $s_i \ne t_i$. It is guaranteed that the input $(u_i, v_i)$ forms a tree, and in the tree rooted at $1$, $s_i$ is an ancestor of $t_i$. | Test Point | Size Limit | Special Property | |:-:|:-:|:-:| | $1 \sim 4$ | $T \le 3000$, $n \le 50$, $m \le 15$, and at most $5$ test cases satisfy $m \ge 10$ | None | | $5 \sim 6$ | $n, m \le 100$, $\sum n^3, \sum m^3 \le 3 \times {10}^7$ | A | | $7$ | $n, m \le 100$, $\sum n^3, \sum m^3 \le 3 \times {10}^7$ | B | | $8$ | $n, m \le 100$, $\sum n^3, \sum m^3 \le 3 \times {10}^7$ | C | | $9$ | $n, m \le 100$, $\sum n^3, \sum m^3 \le 3 \times {10}^7$ | None | | $10 \sim 11$ | $n, m \le 1000$, $\sum n^2, \sum m^2 \le 3 \times {10}^7$ | A | | $12$ | $n, m \le 1000$, $\sum n^2, \sum m^2 \le 3 \times {10}^7$ | B | | $13$ | $n, m \le 1000$, $\sum n^2, \sum m^2 \le 3 \times {10}^7$ | C | | $14 \sim 16$ | $n, m \le 1000$, $\sum n^2, \sum m^2 \le 3 \times {10}^7$ | None | | $17 \sim 18$ | $n, m \le 2 \times {10}^5$, $\sum n, \sum m \le 5 \times {10}^5$ | B | | $19 \sim 20$ | $n, m \le 2 \times {10}^5$, $\sum n, \sum m \le 5 \times {10}^5$ | C | | $21 \sim 23$ | $n, m \le 2 \times {10}^5$, $\sum n, \sum m \le 5 \times {10}^5$ | A | | $24 \sim 25$ | $n, m \le 2 \times {10}^5$, $\sum n, \sum m \le 5 \times {10}^5$ | None | Special property A: It is guaranteed that $n$ is even, and the tree structure is: for any positive integer $1 \le i \le \lfloor \frac{n}{2} \rfloor$, the parent of $2 i$ is $2 i - 1$; if $i \ge 2$, then the parent of $2 i - 1$ is $2 i - 3$. Special property B: It is guaranteed that for all positive integers $1 \le i \le m$, $s_i$ is the parent of $t_i$. Special property C: It is guaranteed that for all positive integers $1 \le i \le m$, $s_i = 1$. Please note that **the difficulty of test points has no direct relationship with their indices**. **【Notes】** Please note that to obtain partial scores, you must ensure that the output format is correct, i.e. output exactly $m$ lines, and each line is an integer. In addition, if for some test case your output is smaller than the correct answer by $1$ rather than larger by $1$, then you **cannot** get $3$ points on this test point. Some test points have a large input size. To optimize the total running time of your program, we suggest using a faster input method. Translated by ChatGPT 5