Problem Description

Given a rooted binary tree with $n$ nodes, the nodes are numbered in order as $1, 2, \dots, n$, and the root node is numbered $1$.

For node $i$, let the index of its left child be $l_i$, and the index of its right child be $r_i$. In particular, if the left child does not exist then $l_i = 0$, and if the right child does not exist then $r_i = 0$.

Each node in the tree corresponds to a subtree rooted at that node. You need to find, among all $n$ subtrees of the given rooted tree, how many of them are full binary trees.

A full binary tree means a binary tree where all leaves have the same depth, and every non-leaf node has exactly two children. For example, the following three binary trees are all full binary trees:

()   ()        ()
    /  \      /  \
   ()  ()   ()    ()
           /  \  /  \
          ()  ()()  ()

In the above binary tree with $3$ nodes, there are $3$ subtrees that are full binary trees (including the whole tree itself and all single leaf nodes).

Another example:

   (1)
   / \
 (2) (3)
     / \
   (4) (5)

In the above binary tree with $5$ nodes, there are $4$ subtrees that are full binary trees (including the subtree rooted at node $3$, and all single leaf nodes).

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the rooted binary tree.

The next $n$ lines each contain two non-negative integers $l_i, r_i$, representing the indices of the left child and right child of node $i$. The integers are separated by spaces.

Output Format

Output one line containing one integer, representing the number of full binary trees among all subtrees.

4
2 3
4 0
0 0
0 0

2

3
2 3
0 0
0 0

3

Hint

Constraints

For $40\%$ of the test points, it is guaranteed that $1 \le n \le 500$.

For all test points, it is guaranteed that $1 \le n \le 10^5$.

Translated by ChatGPT 5