Description
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 200200 points
Problem Statement
You are given a simple undirected graph with
NN vertices and
MM edges. The vertices are numbered
1, \dots, N1,…,N, and the
ii-th
(1 \leq i \leq M)(1≤i≤M) edge connects Vertex
U_iUi and Vertex
V_iVi.
Find the number of tuples of integers
a, b, ca,b,c that satisfy all of the following conditions:
-
1 \leq a \lt b \lt c \leq N1≤a<b<c≤N
-
There is an edge connecting Vertex aa and Vertex bb.
-
There is an edge connecting Vertex bb and Vertex cc.
-
There is an edge connecting Vertex cc and Vertex aa.
Constraints
-
3 \leq N \leq 1003≤N≤100
-
1 \leq M \leq \frac{N(N - 1)}{2}1≤M≤2N(N−1)
-
1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)1≤Ui<Vi≤N(1≤i≤M)
-
(U_i, V_i) \neq (U_j, V_j) \, (i \neq j)(Ui,Vi)=(Uj,Vj)(i=j)
-
All values in input are integers.
Input
Input is given from Standard Input in the following format:
NNMMU_1U1V_1V1\vdots⋮U_MUMV_MVM
Output
Print the answer.
5 6
1 5
4 5
2 3
1 4
3 5
2 5
HINT
(a,b,c)=(1,4,5),(2,3,5) satisfy the conditions.