시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Type checking is the process of verifying that a computer program satisfies the typing rules of a programming language. In some languages this is very difficult, and just checking if two types are equal can be tricky!
For this problem, a type will be represented as a tree made up of nodes. Each node has zero or more child nodes, corresponding to component types. Here is an example of a tree:
Figure 1: A simple finite tree. The root is node 0 and its children are nodes 1 and 2. Node 1 does not have any children, and node 2 has one child (node 3).
Types are allowed to be recursive. This means that 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, which has node 0 as a child, which has node 2 as a child, and so on. The tree keeps going forever, and has been truncated to fit on this page.
Given two possibly infinite trees, your task is to determine whether or not they have the same structure. Two nodes A and B have the same structure if
Two trees have the same structure if their root nodes have the same structure.
Input will consist of a sequence of problems. The first line for each problem will have two space-separated integers, N and M, the number of nodes in the two trees (1 ≤ N, M ≤ 100,000).
The following N lines will describe the first tree. The i'th of these lines (counting from 0) will consist of a number of space-separated integers describing node i. The first integer will be c[i], the number of children that node i has (0 ≤ c[i]; sum of c[i]'s ≤ 100,000). The rest of the line will contain c[i] space-separated integers, the children of node i. The following M lines will describe the second tree similarly. The root of each tree is always node 0.
Each problem will be followed by a blank line. End of input will be denoted by a line with two zeroes (which should not be processed).
For each problem, output "YES" if the two trees have the same structure, or "NO" if they don't.
4 4 2 1 2 0 1 3 0 2 2 1 0 1 3 0 3 4 2 1 2 0 1 0 2 1 2 0 1 3 2 1 2 3 1 2 1 1 2 2 2 2 0 0 2 0 0 0 0
NO YES YES
For the first problem, Figure 1 shows the first tree and the other tree is its mirror image. They have different structures, because the order of the children is significant.
Figure 2 shows the first tree in the second problem. The other tree is represented using more nodes but has the same structure.