Corporate Hierarchy

Recent research from a magazine suggests that employee performance within a company improves when they feel there is no gender discrimination. The study highlights that this "feeling" is not determined by the number of women and men but by the difference in the number of relationships (supervisor - subordinate) where the supervisor is a woman and the subordinate is a man, and vice versa. Specifically, each employee in the company, except for the director, has a direct supervisor who oversees them. For each sequence of employees where each employee is the direct supervisor of the next, the employee at the beginning of the sequence is the supervisor of every other employee in the sequence. Thus, if the hierarchy of the company is represented as a tree with the director as the root, an employee ~x~ is the supervisor of every other employee in the subtree with root employee ~x~.

The study considers pairs of employees of different genders, where the first is the supervisor of the second, not only in a direct relationship but in the entire hierarchy. Specifically, it defines the count ~r_f~ of pairs where the supervisor (in the entire hierarchy) is a woman and the count ~r_m~ of pairs where the supervisor (in the entire hierarchy) is a man. The research argues that employees operate more efficiently when the difference ~r_m - r_f~ approaches ~0~.

Problem:

Develop a program in one of the IOI languages that, after reading the total number of employees in a company and, for each employee, the number (position in the file) of their supervisor and their gender, calculates the difference in pairs of different genders, where the supervisor is a woman, from the pairs where the supervisor is a man.

Input Files:

The input files named company.in are text files with the following structure: The first line contains an integer ~N~, ~1 \le N \le 5.000~, the number of employees in the company. (So employees are numbered from ~1~ to ~N~). In the ~i~-th of the next ~N~ lines, the number of the immediate supervisor of the ~i~-th employee is given. For the director, the number of the immediate supervisor is ~0~. On the same line (~i~-th), a space follows, and the gender of the ~i~-th employee (~m~ for male, ~f~ for female). Consider that no employee is their own supervisor, and the director is the supervisor of every other employee (meaning in the hierarchy of the company it corresponds to a tree with the director as the root).

Output Files:

The output files named company.out are text files with the following structure: In their only line, they have a single integer ~D~, ~-5,000 < D < 5.000~. This number corresponds to the difference ~r_m - r_f~.

Examples of Input - Output Files:

1st

STDIN (company.in)

5
4 m
3 f
4 m
0 f
1 m

STDOUT (company.out)

-2

Graphical Explanation of Example 1.

2nd

STDIN (company.in)

10
3 f
4 f
0 m
3 m
2 m
1 m
4 m
1 m
2 m
1 f

STDOUT (company.out)

0

3d

STDIN (company.in)

10
3 m
4 m
0 f
3 m
2 f
1 m
4 f
1 m
2 f
1 f

STDOUT (company.out)

1

Notes:

1. Maximum execution time: 1 sec.
2. Maximum available memory: 64 MB.
3. All lines terminate with a newline character.