APIO '18 P3 - Duathlon

View as PDF

Submit solution


Points: 20
Time limit: 1.0s
Memory limit: 1G

Problem type

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.

Input

The first line contains integers n and m: number of intersections, and number of roads. Next m lines contain descriptions of roads (1\le n\le 10^5, 1\le m\le 2 \cdot 10^5). Each road is described with pair of integers v_i, u_i, the indices of intersections connected by the road (1 \le v_i, u_i \le n, v_i \neq u_i). For each pair of intersections there is at most one road connecting them.

Output

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.

Scoring

Subtask 1 (points: 5)

n \le 10, m \le 100

Subtask 2 (points: 11)

n \le 50, m \le 100

Subtask 3 (points: 8)

n \le 100\,000, there are at most two roads that ends in each intersection.

Subtask 4 (points: 10)

n \le 1\,000, there are no cycles in the street network. The cycle is the sequence of k (k\ge 3) distinct intersections v_1, v_2, \ldots v_k, such that there is a road connecting v_i with v_{i+1} for all i from 1 to k-1, and there is a road connecting v_k and v_1.

Subtask 5 (points: 13)

n \le 100\,000, there are no cycles in the street network.

Subtask 6 (points: 15)

n \le 1\,000, for each intersection there is at most one cycle that contains it.

Subtask 7 (points: 20)

n \le 100\,000, for each intersection there is at most one cycle that contains it.

Subtask 8 (points: 8)

n \le 1\,000, m \le 2\,000

Subtask 9 (points: 10)

n \le 100\,000, m \le 200\,000

Sample Input 1:

4 3
1 2
2 3
3 4

Sample Output 1:

8

Sample Input 2:

4 4
1 2
2 3
3 4
4 2

Sample Output 2:

14

Explanation

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).


Comments

There are no comments at the moment.