Red-Black Trees

Time limit2sMemory limit1024 MB

Summary

Given a binary tree, count the colorings of its vertices red and black that satisfy the red-black tree rules: no red vertex has a red parent, and every root-to-leaf path has the same number of black vertices.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

The standard libraries of many programming languages implement balanced trees as red-black trees. In this problem you must count the red-black trees of a given shape.

Recall that a binary tree is a set of vertices arranged as a tree. Each vertex has at most two children, one called the left child and the other the right child. The left child, the right child, or both may be absent.

If vertex $Y$ is a child of vertex $X$ , then vertex $X$ is the parent of vertex $Y$ . Every vertex of the tree except one has exactly one parent. The single vertex with no parent is the root of the tree.

Connect every vertex except the root to its parent. For each vertex there is exactly one path from the root to it.

A binary tree is a red-black tree if every vertex is colored red or black and the following conditions hold:

if a vertex is red, its parent is black;
the number of black vertices on the path from the root to any vertex that lacks at least one child is the same.

The figure below shows examples of binary trees whose vertices are colored in two colors.



(а)	(б)	(в)

If the shaded vertices are black and the unshaded ones are red, the tree in figure (а) is a red-black tree, while the trees in figures (б) and (в) are not. The tree in figure (б) violates the first condition: the red vertex 5 has the red parent 2. The tree in figure (в) violates the second condition: the path from the root to vertex 1 contains one black vertex, while the path from the root to vertex 3, for example, contains two.

For a given binary tree, count the ways to color its vertices black and red so that it becomes a red-black tree.

Input

The first line contains the number of vertices $n$ ( $1 \le n \le 1000$ ).

The vertices are numbered from $1$ to $n$ . The next $n$ lines contain two numbers each: for every vertex, the numbers of its left and right children. If a child is absent, its number is given as zero. The input is guaranteed to be correct, that is, the given numbers really define a binary tree.

Output

Print one number: the number of ways to color the vertices of the given binary tree red and black so that it becomes a red-black tree.

Notes

The figure below shows all valid colorings of the tree from the first sample.

Examples2

Example 1
Input
```
6
6 0
1 5
0 0
0 0
3 4
0 0
```
Expected output
```
3
```
Example 2
Input
```
4
2 0
3 0
4 0
0 0
```
Expected output
```
0
```