무한 트리

타입 검사는 프로그램이 프로그래밍 언어의 타입 규칙을 지키는지 확인하는 작업이다. 어떤 언어에서는 이 작업이 무척 어려워서, 두 타입이 같은지 판단하는 것조차 까다롭다.

이 문제에서 타입은 노드로 이루어진 트리로 나타낸다. 각 노드는 자식 노드가 0개 이상 있고, 각 자식은 구성 요소 타입에 대응한다. 다음은 트리의 한 예이다.

그림 1: 간단한 유한 트리. 루트는 노드 0이고, 그 자식은 노드 1과 노드 2이다. 노드 1은 자식이 없고, 노드 2는 자식이 하나(노드 3) 있다.

타입은 재귀적으로 정의해도 된다. 즉 한 노드는 어떤 노드든 자식으로 삼을 수 있고, 부모나 자기 자신도 자식이 될 수 있다. 그러면 트리는 무한해진다.

그림 2: 무한 트리. 노드 0은 노드 2를 자식으로 삼고, 노드 2는 노드 0을 자식으로 삼고, 노드 0은 다시 노드 2를 자식으로 삼는다. 이렇게 트리가 끝없이 이어지므로, 그림은 지면에 맞추어 잘라 그렸다.

무한할 수도 있는 두 트리가 주어진다. 두 트리의 구조가 같은지 판단하는 프로그램을 작성한다. 노드 $A$와 노드 $B$의 구조가 같다는 것은 다음 두 조건이 모두 성립한다는 뜻이다.

• 자식의 개수가 서로 같다.
• 모든 자식 번호 $i$에 대해, $A$의 $i$번째 자식과 $B$의 $i$번째 자식의 구조가 같다.

두 트리의 루트 노드의 구조가 같으면 두 트리의 구조가 같다.

입력은 여러 개의 문제로 이루어진다. 각 문제의 첫 줄에는 두 트리의 노드 개수 $N$과 $M$이 공백으로 구분되어 주어진다 ($1 \le N, M \le 100{,}000$).

이어지는 $N$개의 줄은 첫 번째 트리를 나타낸다. 0번부터 세어 $i$번째 줄에는 노드 $i$를 나타내는 정수가 공백으로 구분되어 주어진다. 첫 번째 정수는 노드 $i$의 자식 개수 $c_i$이고 ($0 \le c_i$, 한 트리의 $c_i$ 총합은 $100{,}000$ 이하), 나머지 $c_i$개의 정수는 노드 $i$의 자식 번호를 순서대로 나열한 것이다. 그다음 $M$개의 줄은 같은 방식으로 두 번째 트리를 나타낸다. 두 트리 모두 루트는 노드 0이다.

각 문제 뒤에는 빈 줄이 하나 온다. 입력의 끝은 0이 두 개만 있는 줄로 나타내고, 이 줄은 처리하지 않는다.

각 문제마다 두 트리의 구조가 같으면 YES를, 다르면 NO를 한 줄에 하나씩 대문자로 출력한다.

첫 번째 예제의 첫째 문제에서 첫 트리는 그림 1의 트리이고, 둘째 트리는 그것을 좌우로 뒤집은 모양이다. 자식의 순서가 중요하므로 두 트리의 구조는 다르다.

그림 2는 첫 번째 예제의 둘째 문제에 나오는 첫 트리이다. 둘째 트리는 노드를 더 많이 쓰지만 구조는 같다.