0084. Matrix Multiplication
| Имя входного файла: | matrix.in |
| Имя выходного файла: | matrix.out |
| Ограничение по времени: | 250 ms |
| Ограничение по памяти: | 16 megabytes |
Let us consider undirected graph G = <V,E > which has N vertices and M edges. Incidence matrix of this graph is 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.
Input file
The first line of the input file contains two integer numbers – N and M (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 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 file
Output the only number – the sum requested.
Examples:
| matrix.in | matrix.out |
|---|---|
| 4 4 1 2 1 3 2 3 2 4 | 18 |
Источник: Petrozavodsk Winter 2003. St. Petersburg Contest II, Thursday, February 06
Обсудить Отправить решение