Same Tree

Problem statement

Two storage systems describe their folder layouts as binary trees. A migration audit must establish whether the layouts agree exactly: matching labels alone are insufficient when a folder occupies a different left or right branch. Your task Determine whether the two binary trees have identical structure and equal values at every corresponding node. Important details Node record indices are local to each input tree and are not labels to compare. Two empty trees match. A left child in one tree cannot match a right child in the other merely because their values are equal. Worked example Two roots valued 4, each with left child 2 and right child 8, describe the same tree and produce true. Moving the child 2 to the right in just one tree would produce false.

Input format

Two consecutive tree descriptions, each using this format: The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print true if the condition holds, otherwise false.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
4 1 2
2 -1 -1
8 -1 -1
3
4 1 2
2 -1 -1
8 -1 -1

Sample output

true