P8489 "Wdoi-(-1)" Fairy Extermination Plan.

This problem is collecting SPJ and testdata.

You are given a tree with $n$ nodes, with nodes numbered from $1$ to $n$. There are $m$ fairies on the tree. Each fairy has a walking route, which can be represented by a sequence $a$ of length $x$. A fairy starts from node $a_1$ and walks along the following cycle: $a_1 \to a_2 \to \cdots \to a_x \to a_1 \to \cdots$. Here, $u \to v$ means walking along the simple path from $u$ to $v$. It is guaranteed that adjacent elements in the sequence $a$ are different. Now, Reimu wants to exterminate the fairies. Each second, each fairy moves one step, and she also moves one step. Try to construct a sequence $b$ of length $l$ such that Reimu walks along the following cycle: $b_1 \to b_2 \to \cdots \to b_l \to b_1 \to \cdots$, and within $9961^{9961^{9961}}$ seconds, she can exterminate all fairies. If at some second Reimu and a fairy are at the same node, or they pass through the same edge at the same time, then she can exterminate that fairy. **It is guaranteed that the given tree is generated by the given random tree generator. However, it is not guaranteed that the routes are randomly generated.** Reimu wants your constructed $l \leq 60$. $1 \leq n \leq 300$.

The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains three positive integers $n, m, seed$, representing the number of nodes in the tree, the number of fairies, and the random seed. Starting from the second line, there are $m$ lines. Each line first contains a positive integer $s$, the number of nodes in the $i$-th fairy's route. Then follow $s$ positive integers $a_{i,1}, a_{i,2}, \dots, a_{i,s}$, representing the $i$-th fairy's route. The tree will be generated by the given random tree generator: ```cpp namespace Gen { mt19937 rnd; int pos[MAXN], deg[MAXN]; vector edges; void calc() { for (int i = 1; i

For each test case, output one line with several integers, representing a sequence $b$ of length $l$.

**[Sample Explanation]** According to the random seed in the sample, you can construct the tree shown in the figure:  It is easy to prove that $\texttt{19 24 17 15 8 16 21 14 19 8 19 13}$ is a node sequence that can exterminate all fairies. Translated by ChatGPT 5