1615 - Matrix:: HUST Online Judge

1615 - Matrix

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 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

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