Hourglass

Interview

Time limit1sMemory limit128 MB

Summary

Count subgraphs formed by two triangles that share exactly one vertex, in an undirected graph with up to 200 vertices.

Level: Medium6 of 10
Topics: Graph, Combinatorics, Brute force, Implementation
Solved: No attempts yet

Problem

Taekhee makes hourglasses. Every day he receives one graph and pulls the hourglasses out of it.

An hourglass looks like this.

More precisely, a subgraph is an hourglass when it satisfies the conditions below.

It consists of exactly two simple cycles of length 3.
The two simple cycles share exactly one vertex.
Edges that join the two simple cycles from outside may be present or absent.

As an example of the third condition, the bold part of the graph below is an hourglass too.

Take two hourglasses, then take the union of their vertices and the union of their edges. If the result equals one of the two hourglasses, the two are the same hourglass. Two hourglasses that fail this condition are different hourglasses.

Taekhee pulls hourglasses out of a graph very fast. With 128MB of memory he counts every distinct hourglass in the graph within 1 second.

Try to match him.

Input

The first line contains the number of vertices $N$ ( $5 \le N \le 200$ ) and the number of edges $M$ ( $6 \le M \le \frac{N(N-1)}{2}$ ) of the graph.

Each of the next $M$ lines describes one edge as $U$ $V$ . ( $1 \le U, V \le N$ , $U \ne V$ )

This means the graph has an edge joining $U$ and $V$ .

There is at most one edge between any two vertices.

Output

Print the number of distinct hourglasses in the graph on the first line.

Count every distinct hourglass, even when two hourglasses share vertices or edges.

Examples3

Example 1
Input
```
5 6
1 2
2 3
3 1
3 4
4 5
5 3
```
Expected output
```
1
```
Example 2
Input
```
5 7
1 2
2 3
3 1
3 4
4 5
5 3
2 4
```
Expected output
```
1
```
Example 3
Input
```
5 6
1 2
1 3
1 4
2 3
2 4
3 4
```
Expected output
```
0
```