Heaps from Trees

Time limit2sMemory limit512 MB

Summary

Given a rooted tree with a value at each node, find the largest subset in which every ancestor-descendant pair has the ancestor's value strictly larger.

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

Problem

You are given a rooted tree with $n$ nodes. The nodes are labeled $1$ to $n$ , and node $1$ is the root. Each node $i$ has a value $v_i$ .

You would like to turn this tree into a heap. That is, you would like to choose the largest possible subset of nodes that satisfies the following heap property: for every pair of nodes $i, j$ in the subset, if node $i$ is an ancestor of node $j$ in the tree, then $v_i > v_j$ .

Equality is not allowed. Find the maximum number of nodes such a subset can contain. The subset does not have to form a subtree.

Input

The input consists of a single test case.

The first line contains a single integer $n$ ( $1 \le n \le 2 \times 10^5$ ), the number of nodes in the tree. The nodes are numbered $1$ to $n$ .

Each of the next $n$ lines describes one node, in order of node number. Line $i$ contains two integers $v_i$ and $p_i$ , where $v_i$ ( $0 \le v_i \le 10^9$ ) is the value of the node and $p_i$ ( $0 \le p_i < i$ ) is the index of its parent. Every node's index is strictly greater than its parent's index. Only node $1$ , the root, has $p_1 = 0$ , since it has no parent. For every other node ( $i = 2, \ldots, n$ ), $1 \le p_i < i$ .

Output

Print a single integer: the number of nodes in the largest subset that satisfies the heap property.

Examples4

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

Example 4

Input

Expected output