Problem Description

In a group of N people, find the celebrity. A celebrity is someone who is known by everyone else but knows no one. Given an N×N matrix where matrix[i][j] = 1 means person i knows person j, find the celebrity or return -1 if none exists.

Input Format

First line contains n (number of people). Next n lines contain n space-separated integers (0 or 1) representing the knows matrix.

Output Format

The index of the celebrity (0-indexed), or -1 if no celebrity exists.

Constraints

• 1 ≤ n ≤ 1000

• matrix[i][j] ∈ {0, 1}

• matrix[i][i] = 0 (person doesn't know themselves)

• Celebrity knows no one: matrix[celebrity][j] = 0 for all j

• Everyone knows celebrity: matrix[i][celebrity] = 1 for all i ≠ celebrity

Sample Input/Output

3
0 1 1
0 0 1
0 0 0

2

Explanation

Person 2 is the celebrity: Person 0 knows 1,2. Person 1 knows 2. Person 2 knows no one. Everyone (0,1) knows person 2, and person 2 knows no one.