Maximum Symmetric Subtree

A weighted binary tree is given. A tree is defined to be symmetric if after swapping the left and right subtrees of every node, the structure of the tree remains the same and corresponding nodes have the same weight. In other words, a binary tree with root T is symmetric if and only if isMirror(T.left, T.right) is true where for any two nodes u and v we define:

[ \text{isMirror}(u,v)=\begin{cases} \text{true} & \text{if both } u \text{ and } v \text{ are null},\ \text{false} & \text{if only one of } u \text{ or } v \text{ is null},\ \bigl(\text{weight}(u)=\text{weight}(v)\bigr) \ \text{and} \ \text{isMirror}(u.left,v.right) \ \text{and} \ \text{isMirror}(u.right,v.left) & \text{otherwise.} \end{cases} ]

Every node in the tree (when considered together with all of its descendants) forms a subtree. Your task is to find a subtree which is symmetric and has the maximum possible number of nodes, and output that number.

Note: A subtree rooted at a node T is defined as the tree consisting of T and all of its descendants. In particular, a single node (with no children) is considered symmetric.

inputFormat

The input begins with a positive integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree. The nodes are numbered from 1 to n, and the tree is rooted at node 1. Each of the following n lines contains three integers:

• w — the weight of the node,
• l — the index of the left child (0 if there is no left child),
• r — the index of the right child (0 if there is no right child).

It is guaranteed that the tree is a valid binary tree.

outputFormat

Output a single integer which is the number of nodes in the largest symmetric subtree of the given binary tree.

sample

1
5 0 0

1