Infinite Trees

Type checking is the process of verifying that a program satisfies the typing rules of a programming language. In some languages this is very difficult, and even deciding whether two types are equal can be tricky.

In this problem a type is a tree made of nodes. Each node has zero or more child nodes, and the children correspond to component types. Here is an example of such a tree.

Figure 1: a simple finite tree. The root is node 0 and its children are nodes 1 and 2. Node 1 has no children, and node 2 has one child, node 3.

Types are allowed to be recursive. A node can have any node as a child, including its parent and even itself. The result is an infinite tree.

Figure 2: an infinite tree. Node 0 has node 2 as a child, node 2 has node 0 as a child, node 0 has node 2 as a child again, and so on. The tree goes on forever, so the picture was cut off to fit on the page.

You are given two trees that may be infinite. Decide whether they have the same structure. Nodes $A$ and $B$ have the same structure when both of these hold.

• They have the same number of children.
• For every child index $i$, the $i$-th child of $A$ and the $i$-th child of $B$ have the same structure.

Two trees have the same structure when their root nodes have the same structure.

The input holds a sequence of problems. The first line of each problem has two space separated integers $N$ and $M$, the number of nodes in the two trees ($1 \le N, M \le 100{,}000$).

The next $N$ lines describe the first tree. Counting from 0, line $i$ holds space separated integers describing node $i$. The first integer is $c_i$, the number of children of node $i$ ($0 \le c_i$, and the sum of $c_i$ over one tree is at most $100{,}000$). The remaining $c_i$ integers are the children of node $i$, listed in order. The next $M$ lines describe the second tree the same way. The root of each tree is node 0.

A blank line follows each problem. The end of the input is a line with two zeroes, which you do not process.

For each problem print YES if the two trees have the same structure, or NO if they do not. Print one answer per line, in uppercase.

In the first problem of the first example the first tree is the tree of Figure 1, and the second tree is its mirror image. The order of the children matters, so the two structures differ.

Figure 2 shows the first tree of the second problem in the first example. The second tree uses more nodes but has the same structure.