Problem1310--同构二叉树

1310: 同构二叉树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 107  Solved: 54
[Submit] [Status] [Web Board] [Creator:]

Description

盗窃团伙麓石开鸡腿xiefang又来盗窃PIPI的资料了,但是这次他们学聪明了,他们会在水印,图标等细微之处改掉PIPI的印记,然后当成自己的产品大卖特卖!
但是他们岂能做得天衣无缝(IQ不足以支撑他们找到所有PIPI标记的地方),所以PIPI开发出一套盗版资料匹配系统,该系统能够把原版资料和盗版资料抽象为两棵二叉树T1和T2。
如果T1可以通过若干次左右孩子互换变成T2,则我们称两棵树是“同构”的。
例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。


                                              图一

                                              图二

Input

第一行按照先序输入T1,其中空节点用 -1 表示。
第二行按照先序输入T2,其中空节点用 -1 表示。

Output

如果两棵树是同构的,也就说明麓石开盗窃了PIPI的资料,输出"YES"。否则输出"NO".

Sample Input

1 2 4 -1 -1 5 6 -1 -1 -1 3 7 8 -1 -1 -1 -1
1 3 7 -1 8 -1 -1 -1 2 5 6 -1 -1 -1 4 -1 -1

Sample Output

YES

Source/Category