The Celebrity Scientist

In a group of n scientists, some scientists may know each other. You are given a matrix representation of the relationships in the form of n binary strings. The j-th character of the i-th string is '1' if scientist i knows scientist j and '0' otherwise.

Your task is to determine if there exists a scientist who is known by all the other scientists. In mathematical terms, you are to find a scientist j such that for all scientists i with \(i \neq j\), the relationship satisfies:

\(\text{relations}[i][j] = '1'\)

If such a scientist exists, output his/her 1-based index; otherwise, output -1. Note that if there is exactly one scientist, then by definition he/she is trivially known by all (since there are no other scientists), so the answer is 1.

inputFormat

The input is provided via standard input (stdin) and is structured as follows:

1. The first line contains an integer n indicating the number of scientists.
2. The following n lines each contain a binary string of length n representing the relationships among scientists.

outputFormat

Output a single integer (stdout): the 1-based index of the scientist who is known by all other scientists, or -1 if no such scientist exists.

4
0111
0011
0001
0000

4