解题思路

• 定义回顾：四个不同点 a,b,c,d 构成“菱形”当且仅当存在有向边 a→b, b→c, a→d, d→c。
• 等价转化：固定一对有序端点 (a,c)，设能把 a 接到 c 的不同中间点（即 a→x 且 x→c 的点）个数为 k，则可由它们两两配对形成 C(k,2) 个菱形。
• 实现：对每个源点 a，遍历所有两步路径 a→b→c，用数组 cnt[c] 统计到该 c 的不同中间点数；只记录出现过的 c（列表 touched），最后对每个被访问的 c 把 C(cnt[c],2) 加入答案。遍历时排除 c==a 和 c==b，同时忽略自环 u==v，以确保四点互异。

复杂度分析

• 总时间复杂度：

题目内容

小明来到一个新的城市，当他看到城市里四个不同的地点 $a、b、c$ 和 $d$ 时，如果存在两条从 $a$ 到 $c$ 的路径————一条通过 $b$ ，另一条通过 $d$，他就称这个四个地点组合为“菱形”。

菱形的定义:

$a、b、c、d$ 四个不同的地点，满足以下条件:

$(a,b)、(b,c)、(a,d)、(d,c)$ 这些道路是直接连接的。

也就是说，$a$ 到 $c$ 有两条不同的路径:一条通过 $b$ ，另一条通过 $d$ .(画出来有可能是凹四面形)

给定一个城市的地点和道路的信息，小明想计算出有多少个“菱形"。

备注:

道路信息是单向的，如 $1$ $2$ 表示从 $1$ 到 $2$ 的单向路径，$2$ $1$ 表示从 $2$ 到 $1$ 的单向路径

输入描述

第一行包含两个整数 $n$ 和 $m$ ($n$ 和 $m$ 使用空格隔开)，其中 $n$ 表示地点的数量，$m$ 表示道路的数量，$n,m(1≤n≤1000，0≤m≤ 10000)$ 。

接下来 $m$ 行每行包含一对整数 $a,b$ 表示有一条从地点 $a$ 到地点 $b$ 的单向道路。

输出描述

输出城市中所有“菱形”的数量。

样例1

输入

4 12
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

输出

12

说明

存在 $12$ 个菱形:

$1->2->3,1->4->3$

$1->2->4,1->3->4$

$2->3->1,2->4->1$

$4->2->1,4->3->1$

$4->1->2,4->3->2$

$4->1->3,4->2->3$

样例2

输入

5 4
1 2
2 3
1 4
4 3

输出

1

说明

存在 $1$ 个菱形：

$1->2->3,1->4->2->3$