Under construction

Still being built. Things may change

Lead or Butterfly

Interview

Time limit1sMemory limit1024 MB

Summary
Count the distinct butterfly subgraphs in a given graph, where a butterfly is a center vertex with two disjoint triangles and two pendant neighbors.
Level

Medium6 of 10

Topics
Graph, Combinatorics, Hash map
Solved
No attempts yet

Problem

Yonghan is afraid of bugs. Seongwoo wants to help Yonghan stop being afraid of them, so he decides to use the butterfly, a pretty insect.

First, Seongwoo draws NN points and MM edges on a very large sheet of paper. Then he picks 7 distinct points in order. Call them a,b,c,d,e,f,ga, b, c, d, e, f, g. If the segments (a,b)(a, b), (b,c)(b, c), (a,c)(a, c), (c,d)(c, d), (c,e)(c, e), (d,e)(d, e), (c,f)(c, f), and (c,g)(c, g) all exist, Seongwoo calls this a 'butterfly'.

For two butterflies, if their sets of edges are the same, the two butterflies are treated as the same butterfly. Any two butterflies that do not satisfy this condition are different butterflies.

Seongwoo wants to know how many different butterflies he can draw. Find this for him.

Note that there is at most one edge between any two points in the given graph, and the order of vertices is not considered.

Input

The first line contains the number of points NN and the number of edges MM. (1≤N≤5001 \leq N \leq 500, 1≤M≤N(N−1)21 \le M \le \frac{N(N-1)}{2})

Each of the next MM lines contains two distinct integers aia_i and bib_i, separated by a space, which are the two endpoints of the ii-th edge, where 1≤i≤M1 \leq i \leq M.

Output

Print the number of different butterflies Seongwoo can draw.

Examples2

  1. Example 1

    Input
    7 8
    1 2
    1 3
    2 3
    1 4
    1 5
    4 5
    1 6
    1 7
    
    Expected output
    1
    
  2. Example 2

    Input
    10 39
    1 3
    2 3
    2 4
    3 4
    1 5
    5 2
    3 5
    4 5
    6 1
    2 6
    3 6
    6 4
    5 6
    1 7
    2 7
    7 3
    4 7
    5 7
    6 7
    8 1
    2 8
    8 3
    5 8
    6 8
    8 7
    9 1
    2 9
    3 9
    4 9
    5 9
    6 9
    7 9
    10 1
    10 2
    4 10
    5 10
    10 6
    10 7
    9 10
    
    Expected output
    11469