Symmetric Tree

Problem statement

A lighting designer arranges lamps as a binary tree around a central support. The design is symmetric only when the two sides mirror each other in both shape and lamp values. Your task Determine whether the binary tree is identical to its own reflection about the root. Important details Compare a left subtree with the mirrored right subtree: left children correspond to right children and vice versa. Equal values on a level alone do not establish symmetry if the missing-child positions differ. An empty tree is symmetric. Worked example Root 1 with leaf children 2 and 2 is symmetric. Changing only the right leaf value to 3 breaks the reflection, producing false.

Input 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
1 1 2
2 -1 -1
2 -1 -1

Sample output

true