The 7th(2012) ACM Programming Contest of HUST - Onsite Contest(Semilive)

From: 2012-12-16 12:10:00 To: 2012-12-16 17:10:00 Now: 2017-09-20 01:10:32 Status: Public

I - Matrix

Time Limit: 3s Memory Limit: 128MB

Submissions: 583 Solved: 171
Description
To efficient calculate the multiplication of a sparse matrix is very useful in industrial filed.
Let's consider this problem:
A is an N*N matrix which only contains 0 or 1. And we want to know the result of A*AT.
Formally, we define B = A*AT, A(i,j) is equal to 1 or 0, and we know the number of  1 in matrix A is M
And your task is to calculate B.
Input
The input contains several test cases. The first line of input contains a integer C indicating the number of the cases.
For each test case, the first line contains two integer N and M.
and each of next M lines contains two integer X and Y, which means A(x,y) is 1.
 
N <= 100,000 M <= 1000.C <= 10 
Output
For each test case, it should have a integer W indicating how many element in Matrix B isn't zero in one line.
Sample Input
2
5 3
1 0
2 1
3 3
3 3
0 0
1 0
2 0
Sample Output
3
9
Hint
AT means the Transpose of matrix A, for more details, AT(i,j) = A(j,i).
eg:
if Matrix A is:
1 2 3
4 5 6
7 8 9
 
then the matrix AT is 
1 4 7
2 5 8
3 6 9
Source
The 7th(2012) ACM Programming Contest of HUST Problem Setter: Zheng Zhang