Lead or Butterfly
InterviewTime limit1sMemory limit1024 MB
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 points and edges on a very large sheet of paper. Then he picks 7 distinct points in order. Call them . If the segments , , , , , , , and 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 and the number of edges . (, )
Each of the next lines contains two distinct integers and , separated by a space, which are the two endpoints of the -th edge, where .
Output
Print the number of different butterflies Seongwoo can draw.