You have organized a party and invited other N−1 friends to the party. Therefore, there are total N friends. Everyone must shake hands with every other person except the people he or she dislikes. There are only 10 people at the party who dislike the other 9 people. The remaining people like everyone who is present at the party. Each friend has its own unique identity number.
Two friends shake hands only if both like each other. In other words, if any of them dislike others, then they cannot shake hands. You must calculate the number of handshakes done at the party.
Input format
- The first line contains a single integer N (10≤N≤109).
- The next 10 lines contain 10 integers each. The first integer in a line represents the unique identity of a friend and the other 9 integers represent the identity number of people it dislikes.
Output format
Print a single integer denoting the total number of handshakes.
Only for explanation purposes, test cases will have only 10*10 dislike matrix.
Input - 10 1 2 4 5 6 2 1 3 8 10 3 1 2 4 10
Output -
35
In the given test case -
1 dislikes 2,4,5,6
2 dislikes 1,3,8,10
3 dislikes 1,2,3,10
so, 1 can handshake with 7,8,9,10 (Not with 3 as 3 dislikes 1 even if 1 likes 3)
Total number of handshakes- 36
