## APIO '18 P3 - Duathlon

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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