뉴턴의 사과

두 이진 트리 $A$와 $B$가 다음 두 조건 중 하나를 만족하면 동등하다(equivalent)고 한다.

1. 두 트리가 모두 비어 있다. 또는
2. 두 트리의 루트 값이 같고, 다음 중 하나가 성립한다.
   • (a) $A$의 왼쪽 서브트리가 $B$의 왼쪽 서브트리와 동등하고, $A$의 오른쪽 서브트리가 $B$의 오른쪽 서브트리와 동등하다. 또는
   • (b) $A$의 왼쪽 서브트리가 $B$의 오른쪽 서브트리와 동등하고, $A$의 오른쪽 서브트리가 $B$의 왼쪽 서브트리와 동등하다.

즉, 각 노드에서 왼쪽과 오른쪽 서브트리를 자유롭게 맞바꿔도 되는 조건에서 두 트리를 모양과 값이 완전히 같게 만들 수 있으면 두 트리는 동등하다.

두 이진 트리가 주어졌을 때, 두 트리가 동등한지 판별하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 두 줄로 이루어지며, 각 줄은 비교할 트리 하나를 나타낸다.

각 트리는 포스트오더(post-order) 순서로 주어진다. 서브트리가 비어 있으면 nil로 표시하고, 각 노드의 데이터는 알파벳 대문자 한 글자이다. 각 줄의 마지막에는 항상 end가 온다.

예를 들어, 한 트리를 포스트오더로 나타내면 다음과 같은 형태이다.

nil nil nil G F nil nil C nil nil E nil D B A end

각 테스트 케이스마다 두 트리가 동등하면 true를, 동등하지 않으면 false를 한 줄에 출력한다.