グラフに含まれる三角形の数を数える
無向グラフが与えられ、頂点の数は
v、辺の数は e です。ここでは、このグラフの中に含まれる三角形の数を数えることが目的となります。グラフにおける三角形とは、3つの頂点がそれぞれ互いに接続し合っているものを指します。
たとえば、図のグラフには以下の3つの三角形が含まれています。
- 1-2-5
- 2-5-4
- 3-2-4
入力
入力の最初の行には、2 つの整数
v (1 ≤ v ≤ 100) と e (1 ≤ e ≤ ) が与えられます。続く
e 行には、v1, v2 (1 ≤ v1, v2 ≤ v) の整数ペアが記述されており、頂点 v1 と頂点 v2 が互いに接続されていることを示します。出力
与えられたグラフに含まれる三角形の数を出力してください。
例
入力 | 出力 |
5 7
1 2
1 5
2 5
4 5
2 4
2 3
3 4 | 3 |
3 2
1 2
2 3 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB