Problem D
Sword Counting


Michael is planning to open a graph store. A graph store is a type of store which specializes in selling various graphs in different sizes and shapes. Michael has done extensive research on the market and the business seems very profitable. He has also invented a graph generator device which is able to produce any graph that he wants.

However, there is one small problem which is keeping him from starting the next booming business: Michael does not know how each graph should be priced. After weeks of reading, he found that a graph’s value can be calculated based on the number of its sword subtrees. A group of six distinct vertices (let’s represent them with letters A to F) form a sword subtree if the following edges exist between them (see figure):

  • A is connected to B.

  • B is connected to A and D.

  • C is connected to D.

  • D is connected to B, C, E, and F.

  • E is connected to D.

  • F is connected to D.

Two sword subtrees $T_1$ and $T_2$ are considered to be different if there is any edge $e$ which exists in $T_1$ but does not exist in $T_2$.

As a highly knowledgeable person and his business partner, your task is to help Michael count the number of sword subtrees in his generated graphs. Given an undirected graph, write a program to count the number of its sword subtrees.


The first line of input will contain two integers $N$ and $M$, $(1 \le N, M \le 100\, 000)$, representing the number of vertices and edges in the graph. The next $M$ lines each will contain two integers $u_ i$ and $v_ i$ $(1 \le u_ i, v_ i \le N$), the endpoints of an undirected edge. It is guaranteed that the graph described by these edges does not contain multiple edges or self loops.


Output a single integer, the number of sword subtrees in the given graph.

Sample Input 1 Sample Output 1
8 7
1 2
1 3
4 1
1 5
5 6
5 7
8 5

Sample Input 2 Sample Output 2
6 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

Please log in to submit a solution to this problem

Log in