401735: GYM100519 G Genealogy

As you may know, the dates in historical documents and descriptions can be given rather inaccurately. It often occurs that in a description of a historic event, the closest thing to a date is something like "In the times of Isaac, the son of Abraham".

The professor Mofenko who is an admirer of alternative history wants to determine the maximum length of the chain of people from father to son that can be composed of people from a given list. With the help of this information, he can invent a lot of amusing alternative histories that are irrefutable by documents.

For each person in the list, his family name, his first name and the first name of his father are given. The family names of a father and his son are always equal. By a happy coincidence, it turned out that all first names of all people in the list are distinct.

The first line of input contains an integer N: the number of the descriptions of people (1 ≤ N ≤ 10⁵).

The next N lines contain the description of a man in the following format: the family name, the first name, the words "son of" and the first name of his father.

All first names and family names start with a capital English letter, and all letters except the first one are lowercase English letters. Consecutive words are separated by a single space character. The length of each first name and each family name is not greater than 10.

Note that it is possible that some person in the list has father outside of the list, but this father shouldn't be included in the chain. It is guaranteed that all N first names of people in the list are pairwise distinct; however, this restriction may not affect first names of people outside of the list.

Output a single integer: the number of people in the longest chain.

7
Bible Isaak son of Abraham
Bible Jacob son of Isaak
Ivanov Ivan son of Petr
Ivanov Protopop son of Vasiliy
Ivanov Vasiliy son of Ivan
Ivanov Petr son of Vasiliy
Bible Judah son of Jacob

4

3
Ivanov Ivan son of Petr
Ivanov Petr son of Vasiliy
Petrov Vasiliy son of Ivan

2

• In the first example, the longest chain is: Ivanov Petr, Ivanov Ivan, Ivanov Vasiliy, Ivanov Protopop.
• In the second example, the longest chain is: Ivanov Petr, Ivanov Ivan.