A9736. Unbearable Controversy of Being
编程题
普及/提高-
知识点
题目描述
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.
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.
输入格式
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.
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.
输出格式
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