Newton's Apple

Two binary trees $A$ and $B$ are said to be equivalent if one of the following holds.

1. Both trees are empty. Or
2. The two roots hold the same value, and at least one of the following is true.
   • (a) The left subtree of $A$ is equivalent to the left subtree of $B$, and the right subtree of $A$ is equivalent to the right subtree of $B$. Or
   • (b) The left subtree of $A$ is equivalent to the right subtree of $B$, and the right subtree of $A$ is equivalent to the left subtree of $B$.

In other words, if you are allowed to freely swap the left and right subtree at every node, two trees are equivalent when they can be made identical in both shape and node values.

Given two binary trees, write a program that determines whether they are equivalent.

The first line contains the number of test cases $T$.

Each test case consists of two lines, and each line describes one tree to compare.

Each tree is given in post-order. An empty subtree is written as nil, and every node's data is a single uppercase letter. Each line always ends with end.

For example, one tree written in post-order looks like this.

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

For each test case, print true if the two trees are equivalent and false otherwise, one result per line.