グラフに含まれるスターグラフの数を数える
無向グラフが与えられており、頂点の数を
v、辺の数を e とします。このとき、グラフに含まれるスターグラフの数を数えてください。スターグラフ(star graph)とは、中心となる頂点が他のすべての頂点と接続されており、その他の頂点は中心の頂点以外には一切接続を持たない構造のグラフを指します。
入力
最初の行には、2つの整数
v (1 ≤ v ≤ 1000) と e (1 ≤ e ≤ 10 000) が与えられます。続く
e 行では、v1、v2 (1 ≤ v1, v2 ≤ v) の形で2つの整数が与えられ、これは v1 と v2 を結ぶ辺を表します。出力
与えられたグラフに含まれるスターグラフの数を出力してください。
例
入力 | 出力 |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | 1 |
8 7
1 5
2 5
3 5
7 5
6 5
4 5
1 8 | 0 |
8 6
1 2
2 3
4 2
5 6
7 6
8 6 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB