Problem Background

The bell rings, and two girls in the computer room stand up from their seats. (Hereafter referred to as $\mathbf{X1}$ and $\mathbf{X2}$)

$\mathbf{X2}$: The training before the provincial selection is really tough... Lectures, exams, reviews, problem-solving — for me now, even thinking about a data structure problem in my dreams would start me thinking involuntarily.

$\mathbf{X1}$: Repetitive training doesn't seem to be a burden for me, but I do feel the joy of problem-solving has gradually diminished recently. Perhaps we need some mental "stimulation": some intellectual games that are not bound by complex techniques, to rekindle our interest in mathematics and algorithms.

$\mathbf{X2}$: Oh, I seem to have received a text message in English, it looks like... some fragments from a math book.

Problem Description

$\mathbf{X1}$: Let me translate the content of the message.

Definition: The trees discussed in this article are inductively defined: a single node constitutes a tree, a tree as a left (or right) child can form a tree, and two trees as left and right children can also form a tree. All structures generated by these rules in a finite number of steps are called trees.

$\mathbf{X2}$: So, the trees mentioned here refer to non-empty, rooted, binary trees with distinct left and right children.

$\mathbf{X1}$: Exactly. Next, the book defines isomorphism between two trees.

Definition: Two trees $T$ and $T^{\prime}$ are said to be isomorphic, denoted as $T \equiv T^{\prime}$, defined by the following four rules:
1. Trees consisting of a single node are mutually isomorphic;
2. If the root nodes of two trees each have only a left subtree, and their left subtrees are isomorphic, then these two trees are isomorphic;
3. If the root nodes of two trees each have only a right subtree, and their right subtrees are isomorphic, then these two trees are isomorphic;
4. If the root nodes of two trees each have both left and right subtrees, and their left and right subtrees are respectively isomorphic, then these two trees are isomorphic.

It is clear that the isomorphism relation forms an equivalence relation on all trees. For convenience, we consider isomorphic trees as identical.

$\mathbf{X2}$: Considering isomorphic trees as identical means the nodes of the trees are identical. Simply put, two trees are isomorphic if and only if they are identical in the sense of unlabeled nodes with distinct left and right children; we say two trees are different if and only if they are not isomorphic.

$\mathbf{X1}$: The book also defines the leaves of a tree: as usual, leaves refer to nodes with no children.

$\mathbf{X2}$: This is consistent with our familiar definition. Mathematicians can be a bit verbose... Only someone like $\mathbf{X3}$ would enjoy this style.

$\mathbf{X1}$: I don't mind it — precise definitions and rigorous proofs are more reassuring than "intuitive" based on experience. Look, the next definition isn't so intuitive.

Definition: A tree $T$ is said to single-step replace into $T^{\prime}$, if replacing a leaf node of $T$ with another tree $T^{\prime \prime}$ results in a tree isomorphic to $T^{\prime}$, denoted as $T \rightarrow T^{\prime}$; A tree $T$ is said to replace into $T^{\prime}$, denoted as $T \rightarrow^{\star} T^{\prime}$, if there exists a natural number $n \geq 1$ and trees $T_{1}, T_{2}, \ldots, T_{n}$, such that $T \equiv T_{1} \rightarrow T_{2} \rightarrow \cdots \rightarrow T_{n} \equiv T^{\prime}$.

$\mathbf{X2}$: Let me think... The replacement means deleting a leaf node and placing another tree at the corresponding position, as if the leaf node "grew" a larger subtree; a tree replaces into another tree if it can be obtained by zero, one, or multiple single-step replacements. Oh... I see! For example, any tree can replace into itself, in other words, for any tree $T$, there is $T \rightarrow^{\star} T^{\prime}$. The following picture can help understand the meaning of single-step replacement and replacement.

$\mathbf{X1}$: You're right. Notably, any tree can replace into infinitely many different trees, and a tree consisting of only one node can replace into any other tree. The book also defines such things.

Definition: For a tree $T$, define $\operatorname{grow}(T)$ as the set of trees that $T$ can replace into, i.e., $\operatorname{grow}(T)=\left\{T^{\prime} \mid T \rightarrow^{\star} T^{\prime}\right\}$. Further, if $\mathscr{T}=\left\{T_{1}, T_{2}, \ldots, T_{n}\right\}$ is a finite set of trees, define $\operatorname{grow}(\mathscr{T})$ as the union of all $\operatorname{grow}\left(T_{i}\right)$, where $i=1,2, \ldots, n$. That is,
$$\operatorname{grow}(\mathscr{T})=\bigcup_{T_{i} \in \mathscr{T}} \operatorname{grow}\left(T_{i}\right)$$

$\mathbf{X2}$: We call $\operatorname{grow}(\mathscr{T})$ the set grown by the collection of trees $\mathscr{T}$ — that is, the set grown by the collection of trees $\mathscr{T}$ includes all trees that can be replaced by some $T \in \mathscr{T}$. Let's call the collection of trees a forest. Loosely speaking, a forest grown by a new forest is all trees in the forest, grown in all possible ways. Obviously, a non-empty forest grown by a forest is an infinite forest. However, this infinite forest, or $\operatorname{grow}(\mathscr{T})$, does not necessarily include all trees — further, it may not even include "almost all" trees.

$\mathbf{X1}$: Let me add: We call a forest almost complete (or say it almost includes all trees) if only finitely many trees are not in it. For a finite forest $\mathscr{T}$, $\operatorname{grow}(\mathscr{T})$ either includes all trees, or almost all trees, or there are infinitely many trees not in it. If this were an OI problem, the problem setter would certainly give examples of the three cases in the sample. The key theorem in the book also uses the same definition as ours.

Theorem (Almost Completeness Decidability): A set of trees is almost complete if only finitely many trees are not in it. Then, for a given finite set of trees $\mathscr{T}$, there exists an efficient algorithm to determine whether $\operatorname{grow}(\mathscr{T})$ is almost complete.

$\mathbf{X2}$: This problem has turned into a pure OI problem! Let me rephrase the problem in our language: Given a finite-sized forest $\mathscr{T}$, determine if $\operatorname{grow}(\mathscr{T})$ is almost complete, i.e., if only finitely many trees cannot be grown from the trees in the forest.

$\mathbf{X1}$: That is, given a finite set of trees $\mathscr{T}$, determine if there are only finitely many trees $T$ such that $T \notin \operatorname{grow}(\mathscr{T})$. The statement $T \notin \operatorname{grow}(\mathscr{T})$ means there is no $T^{\prime} \in \mathscr{T}$ such that $T^{\prime} \rightarrow^{\star} T$. This is indeed very different from the usual OI problems: I haven't even thought of an algorithm for this problem.

$\mathbf{X2}$: Me neither, but I haven't felt this urge to solve an unknown problem in a long time.

Input Format

This problem contains multiple test cases. The first line of the input file contains a positive integer $N$, representing the number of test cases. The following parts contain exactly $N$ test cases, each with the following format:

The first line is a positive integer $m$, representing the number of trees in the set. The next parts describe $m$ trees in the following format:
- First, a positive integer $n$, representing the number of nodes in the tree, with node numbers $1, 2, \ldots, n$;
- The next $n$ lines each contain two non-negative integers, where the $i$-th line from left to right contains $l_i$ and $r_i$, separated by spaces, representing the node numbers of the left and right child nodes of node $i$, respectively. If a left (or right) child does not exist, then $l_i$ (or $r_i$) is $0$. Of course, leaf nodes must satisfy $l_i = r_i = 0$.
- The input data guarantees that a tree with node $1$ as the root node is formed. Note: Node numbers are only for input convenience, and any isomorphic trees are considered identical.

The input $m$ trees may contain isomorphic trees; if these duplicate trees are removed (i.e., each isomorphic tree is left with one), they can form a set of trees $\mathscr{T}$. You need to determine if the set grown by this set of trees $\operatorname{grow}(\mathscr{T})$ is almost complete.

Output Format

The output contains $N$ lines, each representing the answer for the $N$ test cases. The $i$-th line outputs a string: if the set grown by the input set of trees in the $i$-th test case is almost complete (in other words, only finitely many trees cannot be grown from it), then output Almost Complete; otherwise, output No. Note the spelling and capitalization of the output string.

Sample Input and Output

Sample Input #1

1
1
1
0 0

Sample Output #1

Almost Complete

Sample Input #2

1
3
3
2 3
0 0
0 0
2
2 0
0 0
2
0 2
0 0

Sample Output #2

Almost Complete

Sample Input #3

1
2
3
2 3
0 0
0 0
2
2 0
0 0

Sample Output #3

No

Notes/Hints

Sample 2 Explanation

This sample contains only one test case, where the set of trees $\mathscr{T}$ includes three trees, as shown in the figure below. It is easy to find that only trees consisting of a single node are not in $\operatorname{grow}(\mathscr{T})$, which includes almost all trees, thus it is almost complete.

Sample 3 Explanation

This sample contains only one test case, where the set of trees $\mathscr{T}$ includes two trees. It is easy to find that for all $n \geq 2$, chain-like trees with $n$ nodes, where each non-leaf node has only a right child, are not in $\operatorname{grow}(\mathscr{T})$, thus there are infinitely many trees not in $\operatorname{grow}(\mathscr{T})$, so $\mathscr{T}$ is not almost complete.

Sample 4

See the surreal/surreal4.in and surreal/surreal4.ans files in the contestant directory.

Test Point Constraints

All data satisfies: $\sum n \leq 2 \times 10^{6}$, $\sum m \leq 2 \times 10^{6}$, $\max h \leq 2 \times 10^{6}$, $N \leq 10^{2}$. Where, $\sum n$ represents the sum of all node counts in all trees in this test point; $\sum m$ represents the sum of all tree counts in this test point; $\max h$ represents the maximum height of all trees in this test point (a tree with only one node has a height of $1$). The table below describes the data range for each test point, with the same meanings for $\sum n$, $\sum m$, and $\max h$ as above.

Special Properties: Below are explanations for the four special properties mentioned in the table.
- Special Property $1$: For each test case in this test point, $m \leq 4$, i.e., the set of trees includes no more than $4$ trees;
- Special Property $2$: For each test case in this test point, all trees in the set have the same height;
- Special Property $3$: For each test case in this test point, the set of trees only includes chains (in other words, each non-leaf node has only one child);
- Special Property $4$: For each test case in this test point, the set of trees only includes trees that satisfy one of the following two conditions:
- Each non-leaf node has only one child;
- Exactly two leaf nodes have the same parent node, and except for these three nodes, all other nodes have exactly one child.

The specific restrictions for each test point are shown in the table below:

见题面 Input 部分

见题面 Output 部分