Leadership Group Problem

A company’s organizational hierarchy can be represented as a tree. Each member corresponds to a node \(v_i\) in the tree and has an associated level \(w_i\). A smaller \(w_i\) indicates a higher position in the hierarchy. Two members are in the same department if their corresponding nodes are connected by an edge. The leadership group problem is to determine the company’s largest department, i.e. to find a largest subset \(S\) of nodes such that for any two nodes \(v_i, v_j \in S\), if \(v_i\) is a descendant of \(v_j\) then it holds that \(w_{i} \ge w_{j}\) (note that even if two nodes are not adjacent in \(S\), the ancestor–descendant relation in the tree still applies).

Your task is to compute the maximum number of members that can be selected in such a departmental subset from the given leadership tree.

Note: The department does not need to form a connected subtree of the input tree. The only requirement is that if one chosen member is an ancestor of another in the tree, the ancestor’s level is not greater than the descendant’s level (i.e. \(w_{ancestor} \le w_{descendant}\)).

inputFormat

The input begins with an integer \(n\) representing the number of members. Each of the next \(n\) lines contains two integers \(w_i\) and \(p_i\). \(w_i\) is the level of the \(i^{th}\) member, and \(p_i\) is the parent index (0-indexed) of the \(i^{th}\) member. A value of \(-1\) for \(p_i\) indicates that this member is the root of the tree.

outputFormat

Output a single integer: the maximum number of members in a departmental subset of the leadership tree, i.e. the maximum size of a subset \(S\) such that for any two nodes \(v_i, v_j \in S\), if \(v_i\) is a descendant of \(v_j\) then \(w_{i} \ge w_{j}\).

sample

1
5 -1

1