Earliest Ancestor Finder

Given a list of parent-child relationships, find the earliest ancestor of a given person. The earliest ancestor is defined as the individual who is farthest in generational distance from the given person. In case multiple ancestors are found at the same maximum distance, return the one with the smallest numeric value.

If the given person has no parents, output -1.

Relationships are provided as pairs \( (a, b) \) in which \( a \) is a parent of \( b \).

inputFormat

The input begins with an integer \( n \), the number of parent-child relationships.

The following \( n \) lines each contain two integers \( p \) and \( c \), representing that \( p \) is a parent of \( c \).

The last line contains an integer representing the person whose earliest ancestor is to be found.

outputFormat

Output a single integer which is the earliest ancestor. If no ancestors exist for the given person, output -1.

sample

5
1 3
2 3
3 6
5 6
6 7
7

1