Neighbour pairs

In standard drawing of a tree in the plane all nodes of any particular depth lie on one horizontal line.
Let us suppose that each node of a given binary tree is colored while or black.
We say that a pair of nodes (x, y) is a neighbour pair when the depth of x and y is the same, the color of x and y is the same, the keys of x and y are equal and there is no other node of the same color between x and y on the horizontal line connecting x and y in standard drawing.

     


Image 1. Example of a binary tree described in the text. The nodes are identified by the labels, the labels are written in the rectangles at the corresponding nodes. The neighbour pairs are (1, 13), (2, 6), (10, 7).

The task

Find the number of neighbour pairs in a given binary tree.

Input

The input is a binary tree with N nodes, the nodes are labeled by numbers 1 to N in random order, each label is unique. Each node contains an integer key in the range from 0 to 231−1.
The first line of input contains two integers N and R separated by space. N is the number of nodes in the tree, R is the label of the tree root.
Next, there are N lines. Each line describes one node and the order of the nodes is arbitrary. A node is specified by five integer values. The first value is the node label, the second value is the node key, the third and the fourth values represent the labels of the left and right child respectively, and the fifth value represents the node color, white is 0, black is 1. If any of the children does not exist there is value 0 instead of the child label at the corresponding place. The values on the line are separated by a space.
The number of nodes does not exceed 200000.

Output

The output contains a single text line with one integer representing the number of neighbour pairs in the input tree.

Example 1

Input
13 5
7 50 0 0 1
2 70 10 11 0
4 30 9 0 0
6 70 0 0 0
1 90 8 12 0
9 90 0 2 1
13 90 0 6 0
5 30 4 3 0
12 80 0 0 1
10 50 0 0 1
11 50 0 0 0
3 80 1 13 0
8 70 7 0 1
Output
3
The input tree of the example 1 is depicted in the Image 1 above.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set