시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 28 19 11 64.706%

문제

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

You would like to turn this tree into a heap. That is, you would like to choose the largest possible subset of nodes that satisfy this Heap Property: For every node pair i,j in the subset, if node i is an ancestor of node j in the tree, then vi > vj.

Note that equality is not allowed. Figure out the maximum number of nodes you can choose to form such a subset. The subset does not have to form a subtree.

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer n (1 ≤ n ≤ 2 · 105), which is the number of nodes in the tree. The nodes are numbered 1..n.

Each of the next n lines will describe the nodes, in order. They will each contain two integers vi and pi, where vi (0 ≤ vi ≤ 109) is the value in the node, and pi (0 ≤ pi < i) is the index of its parent. Every node’s index will be strictly greater than its parent node’s index. Only node 1, the root, will have p1 = 0, since it has no parent. For all other nodes (i = 2..n), 1 ≤ pi < i.

출력

Output a single integer representing the number of nodes in the largest subset satisfying the Heap Property

예제 입력 1

5
3 0
3 1
3 2
3 3
3 4

예제 출력 1

1

예제 입력 2

5
4 0
3 1
2 2
1 3
0 4

예제 출력 2

5

예제 입력 3

6
3 0
1 1
2 1
3 1
4 1
5 1

예제 출력 3

5

예제 입력 4

11
7 0
8 1
5 1
5 2
4 2
3 2
6 3
6 3
10 4
9 4
11 4

예제 출력 4

7