ILD18ACP - Count Pairs

Given a undirected graph with n vertices and m edges. Your task is count the number of distinct pairs (u, v) that there is exist a path with length exactly 2 from u to v. Another mean, with each pair (u, v), we could find a vertex t that we have an edge (u, t) and (t, v). The input set may be contains multiple edge between any vertex and not consider to connected.

Input

- First line: n, m (1 <= n, m <= 10^5).

- m following line: u, v (1 <= u, v <= n).

Output

The number of distinct pairs.

Example

Input:
5 4
2 1
1 5
3 1
4 3

Output: 4

Note: we have (1, 4), (2, 3), (2, 5), (3, 5)


Added by:Gầy :))
Date:2018-11-16
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2022-02-18 09:18:12
Don't forget the cases of self loop,, and use bitsets.
2020-06-01 23:58:00 Scape
Great problem. Just to clarify, path implies shortest path here. So the answer to @feodorv's test case would be 0.
2020-03-30 00:49:03
What is the answer for the following graph:
2 2
1 2
1 2
?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.