## The Order of the Fox

View as PDF

Points: 20
Time limit: 4.0s
Memory limit: 256M

Author:
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

Canadia has just had one of the worst Christmases ever! All of the Christmas presents vanished on Christmas morning!

You are convinced that the secret society called the "Order of the Fox" is responsible for this theft. To find evidence for this, you decide to examine the layout of the roads and cities of Canadia.

Canadia is a network of cities and bidirectional roads. The -th road connects two distinct cities and , and each pair of distinct cities are linked by at most one road. Two cities are called adjacent if there is a road between them.

A fox pattern is a set of 5 cities and 5 roads so that when these cities and roads are considered in isolation, they have a particular structure (forming a shape similar to that of the head of a fox). Three of the cities must be mutually adjacent (using 3 of the 5 roads), forming a triangle. The remaining two cities must each be adjacent to a city in the triangle (using the remaining 2 of the 5 roads). Moreover, the cities in the triangle that the two remaining cities are adjacent to must be different.

Count the number of subsets of cities and roads that form a fox pattern, modulo .

#### Constraints

and each pair of distinct cities are linked by at most one road.

#### Input Specification

The first line contains two space-separated integers and .

lines follow; the -th one contains two space-separated integers .

#### Output Specification

Output a single integer: the number of fox patterns modulo .

#### Sample Input 1

5 5
1 2
2 3
3 1
3 4
2 5

#### Output for Sample Input 1

1

#### Explanation for Sample Input 1

The whole network forms a fox pattern.

#### Sample Input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

#### Output for Sample Input 2

60