You are in a party of N people, where only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. Your task is to find the stranger (celebrity) in party.

You are in a party of N people, where only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone at the party. Your task is to find the stranger (celebrity) at the party.

You will be given a square matrix M[][] where if an element of row i and column j  is set to 1 it means the ith person knows the jth person. You need to complete the function getId() which finds the id of the celebrity if present else returns -1. The function getId() takes two arguments, the square matrix M and its size N.

M[i][i] will be equal to zero always.

For each test, the case output will be the id of the celebrity if present (0 based index). Else -1 will be printed.

Example:
Input :
2
3
0 1 0 0 0 0 0 1 0
2
0 1 1 0
Output :
1
-1

Explanation :
Testcase 1:
For the above test case, the matrix will look like
0 1 0 
0 0 0
0 1 0
Here,  the celebrity is the person with index 1 ie id 1
Testcase 2:
The matrix will look like
0 1
1 0
Here, there is no such person who is a celebrity (a celebrity should know no one).

// { Driver Code Starts

#include<bits/stdc++.h>

using namespace std;

#define MAX 501

int getId(int M[MAX][MAX],int n);

int main()

{

    int T;

    cin>>T;

    int M[MAX][MAX];

    while(T--)

    {

        int N;

        cin>>N;

        memset(M,0,sizeof M);

        for(int i=0;i<N;i++)

        {

            for(int j=0;j<N;j++)

            {

                cin>>M[i][j];

            }

        }

        cout<<getId(M,N)<<endl;

    }

}

// } Driver Code Ends

// The task is to complete this function

// M[][]: input matrix

// n: size of matrix (n*n)

int getId(int M[MAX][MAX], int n)

{

    //Your code here

    stack<int> s;

    for(int i=0;i<n;++i)

    {

        s.push(i);

    }

    int j;

    while(s.size()>1)//when element is greater than 1

    {

//pop two element and checking m[i][j] is 1 that mean i know j so push j.

        int i=s.top();

        s.pop();

         j=s.top();

        s.pop();

        

        if(M[i][j]==1)

        {

            s.push(j);//j is not know i but i know j

        }else{

            s.push(i);// i is not know j but j know i

        }

    }

    'int   k;

            k=s.top(); //last element in stack which has probability to strange
            s.pop();
            for(int i=0;i<n;++i)
              {

               //if m[k][i] is 1 that mean k know i so k is not strange

               //if m[i][k] is 0 that mean i don't know k 
                  if(k!=i&&((M[k][i]==1)||(M[i][k]==0)))
                  {
                    return -1;
                  }
              }
    
    return k;
    

}