Find the Celebrity

You are given a party with n people (numbered from 0 to n-1) and an n x n matrix M where M[i][j] = 1 means person i knows person j and 0 means they do not. A celebrity is defined as someone who is known by everyone else but who knows no one. In other words, person c is a celebrity if for every person i (with i ≠ c), the following conditions hold:

• \(M[i][c] = 1\)
• \(M[c][i] = 0\)

Your task is to determine the celebrity's index. If there is no celebrity, print -1.

Note: The input is provided in stdin and your output must be printed to stdout.

inputFormat

The first line contains one integer n representing the number of people at the party. The following n lines each contain n space-separated integers (either 0 or 1) representing the matrix M. The element at the ith row and jth column indicates whether person i knows person j (1 for yes, 0 for no). Diagonal elements of the matrix will always be 0.

outputFormat

Print a single integer which is the index of the celebrity if one exists; otherwise, print -1.

4
0 1 1 0
0 0 1 1
0 0 0 0
1 1 1 0

2