CF489D.Unbearable Controversy of Being
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Tomash keeps wandering off and getting lost while he is walking along the streets of Berland. It's no surprise! In his home town, for any pair of intersections there is exactly one way to walk from one intersection to the other one. The capital of Berland is very different!
Tomash has noticed that even simple cases of ambiguity confuse him. So, when he sees a group of four distinct intersections a, b, c and d, such that there are two paths from a to c — one through b and the other one through d, he calls the group a "damn rhombus". Note that pairs (a, b), (b, c), (a, d), (d, c) should be directly connected by the roads. Schematically, a damn rhombus is shown on the figure below:

Other roads between any of the intersections don't make the rhombus any more appealing to Tomash, so the four intersections remain a "damn rhombus" for him.
Given that the capital of Berland has n intersections and m roads and all roads are unidirectional and are known in advance, find the number of "damn rhombi" in the city.
When rhombi are compared, the order of intersections b and d doesn't matter.
托马什在贝尔兰的街道上行走时总是走神迷路,这并不奇怪!在他的家乡,任意两个路口之间都恰好存在一条路径。而贝尔兰首都的情况则大不相同!
托马什发现,即便是最简单的歧义情形也会让他困惑。因此,当他看到四个互不相同的路口 a、b、c 和 d,使得从 a 到 c 存在两条路径——一条经过 b,另一条经过 d 时,他就将这组路口称为一个“该死的菱形”。注意:点对 (a,b)、(b,c)、(a,d)、(d,c) 必须由道路直接相连。该“该死的菱形”的示意图如下所示:

任意两个路口之间是否存在其他道路,并不会影响托马什对该菱形的判定——这四个路口仍被他视为一个“该死的菱形”。
已知贝尔兰首都共有 n 个路口和 m 条道路,所有道路均为单向,且其连接关系预先已知。请计算该城市中“该死的菱形”的数量。
在比较不同菱形时,路口 b 与 d 的顺序无关(即 {a,b,c,d} 与 {a,d,c,b} 视为同一个菱形)。
输入格式
The first line of the input contains a pair of integers n, m (1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000) — the number of intersections and roads, respectively. Next m lines list the roads, one per line. Each of the roads is given by a pair of integers a__i, b__i (1 ≤ a__i, b__i ≤ n;a__i ≠ b__i) — the number of the intersection it goes out from and the number of the intersection it leads to. Between a pair of intersections there is at most one road in each of the two directions.
It is not guaranteed that you can get from any intersection to any other one.
输入的第一行包含两个整数 n、m(1 ≤ n ≤ 3000,0 ≤ m ≤ 30000),分别表示交叉路口的数量和道路的数量。接下来的 m 行每行描述一条道路。每条道路由一对整数 ai、bi(1 ≤ ai, bi ≤ n;ai = bi)给出,分别表示该道路的起点交叉路口编号和终点交叉路口编号。任意两个交叉路口之间,在每个方向上至多只有一条道路。
不能保证从任意一个交叉路口都可以到达其他任意一个交叉路口。
输出格式
Print the required number of "damn rhombi".
打印所需数量的“该死的菱形”。
输入输出样例
输入#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
输入解题思路,AI测评打分。不知道怎么写?