Woburn Challenge 1999
Brad Pitt's Fight Club has become quite big and so he wants to put some kind of organization into it. But remember the first two rules of Fight Club. No one can talk about Fight Club. But just on the off-chance that one of his minions loses his negligible mind in a fight and does talk about Fight Club, he wants to ensure that the entire organization is not compromised. So he does the following: He assigns one of his lackeys to come up with an organizational hierarchy subject to a few rules
- A person at a certain level is in charge of everyone below him in the hierarchy and knows the identity of ONLY those below him(thus, he can only compromise those below him)
- Everyone has exactly ~1~ person in charge of them, except Brad Pitt (see below). Why? Think about how the club would be compromised if this was not followed.
- Brad Pitt is the head of the hierarchy and thus has no boss. Therefore, no one knows his identity but conversely, he knows the identity of everybody (because everybody is under him).
This is all good, but we're forgetting that his followers are not exactly rocket scientists and so the man in charge of doing the hierarchy forgot to label the people in the hierarchy with their names. For extra security, everyone was labeled with a positive integer ~n~ ~(0 < n \le 20\,000)~. As a result, Brad Pitt doesn't know where he is on the hierarchy; to find out, he needs to scan the entire list. However, he doesn't even know if his rules were followed (writer's note: you just can't hire good help these days). So your job is a) to determine if the rules were followed and b) if so, determine which person in the list represents Pitt.
We will give you the hierarchy with numbers in place of the people in
the hierarchy. If the rules were not followed, output
Otherwise, output the number of the person that corresponds to Brad
Pitt. (Note: you can safely assume that a valid hierarchy was not the
result of multiple mistakes).
The input will be pairs of integers ~x~, ~y~, such that ~x~ is a boss of ~y~. The
numbers will be separated by (possibly multiple) white spaces (this
includes returns!). The total number of people will be less than ~200~ and
each boss will have no more than ~10~ people IMMEDIATELY below him (even
in an invalid hierarchy). An input of
0 0 terminates the current
-1 -1 denotes the end of data.
For each given hierarchy, output
INVALID if the rules were not
followed and Brad Pitt's number otherwise.
3 1 3 2 2 4 0 0 3 1 1 3 0 0 -1 -1