William Wilson P44991

Statement

thehtml

My namesake was born on precisely the day of my own nativity…The same name! The same contour of person!…And then his dogged and meaningless imitation of my gait, my voice, my habits, and my manner!…I plunged my sword, with brute ferocity, repeatedly through and through his bosom…“You have conquered, and I yield…In me didst thou exist—and, in my death, see by this image, which is thine own, how utterly thou hast murdered thyself.”

William murdered his alter-ego (let us call him X), so similar to William that they could be twin brothers. To find out, William gathered information about his own family and about the family of X. William got a tree with the most notorious physical characteristics of some of his ancestors, each codified with a natural number. The characteristic of William is at the root. For each node, its left child contains the characteristic of its father, while its right child contains the characteristic of its mother. (For instance, if William’s genealogical tree is the first tree below, and a 2 codifies having green eyes, then the mother of the father of William had green eyes.)

[levelsep=31pt,treesep=15pt]3 0 7 4 2 5 4 7 7 [levelsep=31pt,treesep=15pt]3 5 4 7 7 0 2 7 4

Unfortunately, William does not know the gender of any of the ancestors of X, so he draws them left or right arbitrarily in X’s tree. (For instance, if X’s tree is the second tree above, then any of the four grandparents of X could have green eyes.) Consequently, William has decided to consider X his twin brother if and only if it is possible to transform X’s tree into William’s tree by repeatedly choosing any of its nodes and swapping its two children.

Please write a program to decide if two given genealogical trees can correspond to twin brothers, according to William’s convention.

Input

Input consists of several cases. Every case begins with its two names, made up of only letters. Follow two binary trees, described with their respective preorders, using -1 to mark empty subtrees. Each given tree has at most 2¹⁰ nodes.

Output

For every case, print the correct answer.

Public test cases

Input

William X
3 0 7 -1 4 -1 -1 2 -1 -1 5 4 -1 -1 7 7 -1 -1 -1
3 5 4 -1 -1 7 -1 7 -1 -1 0 2 -1 -1 7 -1 4 -1 -1
John Jack
2 -1 -1
3 -1 -1
Mary Ann
4000000 -1 -1
-1
Peter Tom
3 -1 5 -1 -1
5 -1 3 -1 -1
Edgar Allan
3 -1 5 -1 -1
3 5 -1 -1 -1

Output

William and X can be twins.
John and Jack cannot be twins.
Mary and Ann cannot be twins.
Peter and Tom cannot be twins.
Edgar and Allan can be twins.

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++