Tree Isomorphism

Bilbo meets the love of his life, Oblib, but she seems eerily familiar, and he worries that they might be related. They both know their ancestry, yet they cannot simply compare their family trees: Bilbo knows his ancestors' names in the male form, while Oblib knows hers in the female form, and the two forms are unrelated. Even if they were brother and sister, every ancestor name they know would be different!

Bilbo and Oblib have written out their family trees. Your task is to decide whether the two trees are isomorphic — that is, whether there is a one-to-one correspondence between their nodes that preserves the parent–child structure, ignoring the names. The trees are rooted, so their roots are fixed and must map to each other.

As an example, the two trees on the left below are not isomorphic: there is no way to match the two children of a with the two children of x, because one child of a must have two children of its own, but neither child of x does.

Non-isomorphic trees	Isomorphic trees

The two trees on the right, however, are isomorphic. One valid mapping is: a ↔ x (the roots always map to each other), b ↔ z, c ↔ y, g ↔ u, d ↔ w, e ↔ t, f ↔ v. There is one other isomorphism as well (it swaps the images of d and e).

The first line contains the number of test cases $T$ ($T < 100$). Each test case consists of two lines, each describing one tree.

A tree is given by the node labels encountered during a pre-order traversal that starts at the root: the tree is walked from the root toward the leaves and from left to right, printing every node's label as it is first visited. Immediately after all children of a node have been listed, a hash mark # is printed to close that node. All labels and hash marks are separated by single spaces.

For instance, the tree rooted at a with children b (whose children are the leaves d and e) and the leaf c is written as a b d # e # # c # #.

For each test case, print The two trees are isomorphic. if the two trees are isomorphic, or The two trees are not isomorphic. if they are not. End each line with a newline.