New Year's '19 P7 - The Order of the Fox

View as PDF

Submit solution

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

Problem type

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 N cities and M bidirectional roads. The i-th road connects two distinct cities a_i and b_i, 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 10^9+7.


5 \le N \le 300\,000

5 \le M \le 300\,000

1 \le a_i, b_i \le N

a_i \ne b_i and each pair of distinct cities are linked by at most one road.

Input Specification

The first line contains two space-separated integers N and M.

M lines follow; the i-th one contains two space-separated integers a_i, b_i.

Output Specification

Output a single integer: the number of fox patterns modulo 10^9+7.

Sample Input 1

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

Sample Output 1


Explanation for Sample Output 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

Sample Output 2



There are no comments at the moment.