Almost Complete Forest

Given a finite set of trees (a forest) \(\mathscr{T}\) under the following inductive definition, determine whether its grow set is almost complete, i.e. whether there exist only finitely many trees not contained in it.

Tree Definition:

• A single node is a tree. We represent a leaf node as 0.
• If \(T\) is a tree, then 1X is a tree representing a node with only a left child, where X is the encoding of \(T\).
• If \(T\) is a tree, then 2X is a tree representing a node with only a right child, where X encodes \(T\).
• If \(T_1\) and \(T_2\) are trees, then 3XY is a tree representing a node with both left and right children, with X and Y encoding \(T_1\) and \(T_2\), respectively.

A tree growth operation is defined as a single-step replacement: given a tree \(T\), replacing one of its leaf nodes by another tree \(T'\) yields a new tree (up to isomorphism, where isomorphism means that the trees are identical in structure when node labels are ignored and left/right child distinction is maintained). Denote \(T \rightarrow T'\) if \(T'\) is obtained by a single-step replacement on \(T\). The transitive closure \(T \rightarrow^\star T'\) allows zero or more such replacement steps (note: by convention, \(T \rightarrow^\star T\) since zero steps are allowed).

For a tree \(T\), define \(\operatorname{grow}(T) = \{T' \mid T \rightarrow^\star T'\}\). For a forest \(\mathscr{T}\), define \(\operatorname{grow}(\mathscr{T}) = \bigcup_{T \in \mathscr{T}} \operatorname{grow}(T)\). The forest is almost complete if there exist only finitely many trees that do not belong to \(\operatorname{grow}(\mathscr{T})\).

Observation: It turns out that a necessary and sufficient condition for \(\operatorname{grow}(\mathscr{T})\) to be almost complete is that \(\mathscr{T}\) contains the single-node tree (i.e. the tree encoded as 0). This is because every non-empty tree (under our inductive definition) contains at least one node, and thus every tree can be grown from a single-node tree. Otherwise, if no tree in \(\mathscr{T}\) is 0, then there exist infinitely many trees that cannot be grown from \(\mathscr{T}\>.

Task: Given a finite forest \(\mathscr{T}\) (of size \(n\)) in the specified encoding, determine if \(\operatorname{grow}(\mathscr{T})\) is almost complete. Print Yes if it is almost complete and No otherwise.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 100\)), the number of trees in the forest. The following \(n\) lines each contain a non-empty string representing a tree in the encoding described above.

Encoding details:

• 0: a leaf node.
• 1X: a node with only a left child (where X is the encoding of the left subtree).
• 2X: a node with only a right child (where X is the encoding of the right subtree).
• 3XY: a node with both left and right children (where X and Y are the encodings of the left and right subtrees, respectively).

outputFormat

Output a single line: Yes if \(\operatorname{grow}(\mathscr{T})\) is almost complete; otherwise output No.

sample

1
0

Yes