← 返回题目列表

Codeforces · 489/D

D. 无法忍受的存在争议

中文机器翻译题面 查看原题

托马什(Tomash)沿着贝尔兰(Berland)的街道行走时不断徘徊并迷路。这并不奇怪!在他的家乡,对于任何一对十字路口,从一个十字路口步行到另一个十字路口都只有一种方法。贝尔兰的首都很不一样!

托马什注意到,即使是简单的歧义案例也会让他感到困惑。因此,当他看到一组四个不同的交叉点 a、b、c 和 d 时,从 a 到 c 有两条路径——一条通过 b,另一条通过 d,他称该组为“该死的菱形”。请注意,对 (a, b)、(b, c)、(a, d)、(d, c) 应由道路直接连接。下图显示了一个该死的菱形:

任何十字路口之间的其他道路都不会使菱形对托马什更具吸引力,因此这四个十字路口对他来说仍然是“该死的菱形”。

鉴于 Berland 首都有 n 个十字路口和 m 条道路,并且所有道路都是单向的并且事先已知,请找出该城市中“该死的菱形”的数量。

比较菱形时,交点 b 和 d 的顺序并不重要。

输入

输入的第一行包含一对整数 n, m (1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000) — 分别是交叉口和道路的数量。接下来的 m 行列出了道路,每行一条。每条道路都由一对整数 ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi) 给出——它发出的路口编号和通向的路口编号。在一对交叉路口之间,两个方向各最多有一条道路。

不保证您可以从任一路口到达任何其他路口。

输出

打印所需数量的“该死的菱形”。

示例

输入 #1

5 4
1 2
2 3
1 4
4 3

输出 #1

1

输入 #2

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

输出 #2

12