Find the Celebrity

Among n people, a celebrity is known by everyone but knows nobody. Return the celebrity index or -1. Pattern focus: Adjacency Matrix. The knows relation is naturally represented as a matrix or oracle query.

Input Format

n = number of people, knows = matrix where knows[i][j] indicates whether i knows j

Output Format

index of the celebrity, or -1 if none exists

Constraints

• 1 <= input size <= 10^5
• -10^9 <= numeric values <= 10^9
• n, knows must satisfy the format described in inputFormat.

Examples

n = 3
knows = [[0,1,1],[0,0,1],[0,0,0]]

2

n = 2
knows = [[0,1],[0,0]]

1