A village has n people labelled 1 to n. A survey collected pairs [a, b] meaning "a trusts b". The villagers say there may be one referee: a person who trusts nobody, while every other villager trusts them.
Implement find_trusted(n: int, trust: list[list[int]]) -> int: return the referee's label, or -1 if nobody fits.
find_trusted(3, [[1, 3], [2, 3]]) # 3
find_trusted(3, [[1, 3], [2, 3], [3, 1]]) # -1 (3 trusts someone)
find_trusted(4, [[1, 2], [3, 2], [1, 3]]) # -1 (4 doesn't trust 2)
find_trusted(1, []) # 1 (alone, trusting nobody)
1 <= n <= 100,000, up to 200,000 pairs. Pairs are distinct and nobody trusts themselves.- Aim for O(n + number of pairs).
Show hint
For each person, two numbers settle the question: how many people trust them, and how many they trust.