The Party Celebrity

At a party there are n guests, numbered 0 to n - 1. Each pair [a, b] in knows means guest a knows guest b. Knowing goes one way: a can know b without b knowing a.

A celebrity is a guest whom every other guest knows, but who knows none of the other guests. Write find_celebrity(n, knows) that returns the celebrity's number, or -1 if the party has no celebrity.

Examples

find_celebrity(3, [[0, 1], [2, 1], [0, 2]])  # returns 1
find_celebrity(3, [[0, 1], [1, 0], [2, 1]])  # returns -1
find_celebrity(1, [])  # returns 0

In the first party, guests 0 and 2 both know guest 1, and guest 1 knows nobody. In the second, everyone knows guest 1, but guest 1 knows guest 0, so guest 1 is not a celebrity. With only one guest there is nobody else to know, so that guest is the celebrity.

Note

• 1 <= n <= 1000. No pair appears twice, and nobody is listed as knowing themselves.
• A party can never have two celebrities: each would have to know the other.