All problems

Find the Town Judge

Easy · graph traversal

A town has n people, labelled 1 to n. Rumour says one of them is a secret judge. If the judge exists, two things are true:

• The judge trusts nobody.
• Every other person trusts the judge.

You are given the list trust. Each entry [a, b] means person a trusts person b. Trust goes one way only: [a, b] says nothing about whether b trusts a. No pair is listed twice and nobody trusts themselves.

Return the label of the judge. If there is no person who fits both rules, return -1. (At most one person can fit them.)

Examples

Example 1

Input: n = 3, trust = [[1, 3], [2, 3]]

Output: 3

Persons 1 and 2 both trust person 3, and person 3 trusts nobody.

Example 2

Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]

Output: -1

Person 3 trusts person 1, so person 3 cannot be the judge, and nobody else is trusted by everyone.

Example 3

Input: n = 1, trust = []

Output: 1

A town of one person: they trust nobody, and there is nobody else who needs to trust them.

Constraints

• 1 <= n <= 1000
• 0 <= len(trust) <= 10^4
• Each entry holds two different labels in the range 1 to n.
• No pair appears more than once.