| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 200 | 74 | 59 | 34.503% |
The Byteburg’s street network consists of n intersections linked by m two-way street segments. Recently, the Byteburg was chosen to host the upcoming duathlon championship. This competition consists of two legs: a running leg, followed by a cycling leg.
The route for the competition should be constructed in the following way. First, three distinct intersections s, c, and f should be chosen for start, change and finish stations. Then the route for the competition should be built. The route should start in s, go through c and end in f. For safety reasons, the route should visit each intersection at most once.
Before planning the route, the mayor wants to calculate the number of ways to choose intersections s, c, and f in such a way that it is possible to build the route for them. Help him to calculate this number.
The first line contains integers n and m: number of intersections, and number of roads. Next m lines contain descriptions of roads (1 ≤ n ≤ 105, 1 ≤ m ≤ 2 · 105). Each road is described with pair of integers vi, ui, the indices of intersections connected by the road (1 ≤ vi, ui ≤ n, vi ≠ ui). For each pair of intersections there is at most one road connecting them.
Output the number of ways to choose intersections s, c, and f for start, change and finish stations, in such a way that it is possible to build the route for competition
4 3 1 2 2 3 3 4
8
4 4 1 2 2 3 3 4 4 2
14
In the first example there are 8 ways to choose the triple (s, c, f): (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 2, 1), (4, 2, 1), (4, 3, 1), (4, 3, 2).
In the second example there are 14 ways to choose the triple (s, c, f): (1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 3), (2, 3, 4), (2, 4, 3), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2).