VIP - VIP
One day there was a party in the town. A VIP was invited to the party - a person that is known by everyone in the town, while he himself does not know anyone.
Write a computer program that finds the VIP in a crowd of people.
Input
The first line of the input contains one integer d (1 <= d <= 100), which indicates the number of data sets.
Each set consists of several lines. The first line contains a natural number n (1 <= n <= 500), which indicates the number of people present at the event. The next n lines each contain n numbers 0 or 1. Such a number in the i-th row and j-th column means:
- 0 - i-th person does not know j-th person,
- 1 - i-th person knows j-th person.
Each person knows himself.
We know that VIP exists, i.e., there is a person whom is known by everyone and who knows no one but himself
Output
Output one number for each data set, meaning the number of the person who is a VIP.
Example
Input: 2
3
1 0 1
1 1 1
0 0 1
5
1 0 0 1 1
1 1 0 1 0
0 0 1 1 1
0 0 0 1 0
1 1 0 1 1 Output: 3
4
Added by: | Rafał Witkowski |
Date: | 2022-03-15 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | It was presented by Piotr Zieliński to watch candidate ability to participate in programming cotenst |