## APIO '18 P3 - Duathlon

View as PDF

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

Problem type

The Byteburg's street network consists of intersections linked by 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 , , and should be chosen for start, change and finish stations. Then the route for the competition should be built. The route should start in , go through and end in . 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 , , and 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 and : number of intersections, and number of roads. Next lines contain descriptions of roads (, ). Each road is described with pair of integers , , the indices of intersections connected by the road (, ). For each pair of intersections there is at most one road connecting them.

Output

Output the number of ways to choose intersections , , and for start, change and finish stations, in such a way that it is possible to build the route for competition.

Scoring

,

,

, there are at most two roads that ends in each intersection.

, there are no cycles in the street network. The cycle is the sequence of () distinct intersections , such that there is a road connecting with for all from 1 to , and there is a road connecting and .

, there are no cycles in the street network.

, for each intersection there is at most one cycle that contains it.

, for each intersection there is at most one cycle that contains it.

,

,

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 : , , , , , , , .

In the second example there are 14 ways to choose the triple : , , , , , , , , , , , , , .