SGU 196 – Matrix Multiplication

Let us consider an undirected graph G = <V, E> which has N vertices and M edges. Incidence matrix of this graph is an N × M matrix A = {aij}, such that aij is 1 if i-th vertex is one of the ends of j-th edge and 0 in the other case. Your task is to find the sum of all elements of the matrix ATA where AT is A transposed, i.e. an M × N matrix obtained from A by turning its columns to rows and vice versa.

Input

The first line of the input file contains two integer numbers — N and M (2 le N le 10,000, 1 le M le 100,000). 2M integer numbers follow, forming M pairs, each pair describes one edge of the graph. All edges are different and there are no loops (i.e. edge ends are distinct).

Output

Output the only number — the sum requested.

Sample test(s) Input 4 4 1 2 1 3 2 3 2 4 Output 18 给定一个有N个顶点，M条边的图，N M的矩阵A中的元素a（i，j）为1当且仅当第i个顶点是第j条边的端点，否则为零。求A\'A的各个元素之和。

``````#include <stdio.h>
int a[10005]={0};
int b[100005][2];
int main()
{
int n,m;
int ans=0;
int x,y,i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
b[i][0]=x;
b[i][1]=y;
a[x]++;
a[y]++;
}

for(i=1;i<=m;i++)
{
ans+=a[b[i][0]]+a[b[i][1]];
}
printf("%dn",ans);
return 0;
}``````