D - The Big Two 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

あるゲームには N 人のプレイヤー 1,2,\dots,N がいます。
このゲームは 2 人のプレイヤーが 1 対 1 で戦う形式です。
N 人のプレイヤーによるトーナメント戦が M 回行われ、m 回目のトーナメント戦の決勝にはプレイヤー A_m,B_m の 2 人が勝ち上がりました。
以下の条件を満たすような 2 整数 x,y の組がいくつあるかを求めてください。

  • 1 \leq x \lt y \leq N
  • どのトーナメント戦においても、プレイヤー x とプレイヤー y の少なくとも一方が決勝に勝ち上がっている

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M  
A_1 B_1  
A_2 B_2  
\vdots  
A_M B_M

出力

答えを 1 行で出力せよ。

入力例 1

5 5
1 2
3 4
1 3
2 3
2 5

出力例 1

1

(x,y)=(2,3) のとき条件は満たされ、それ以外のとき条件は満たされません。
たとえば 4 回目のトーナメントではプレイヤー 1,4 はいずれも決勝に勝ち上がっていないので、(x,y)=(1,4) は条件を満たしません。

入力例 2

7 8
2 4
1 3
1 7
1 3
1 2
1 6
1 5
1 3

出力例 2

2

条件を満たす (x,y) の組は、(1,2),(1,4) の 2 つです。

入力例 3

5 8
1 2
2 4
1 3
1 3
1 2
1 2
1 5
1 2

出力例 3

2

Score : 400 points

Problem Statement

There is a game with N players 1,2,\dots,N.
This game is played in a format where two players face each other one-on-one.
A tournament among the N players was held M times, and the two players A_m and B_m advanced to the final of the m-th tournament.
Find the number of pairs of integers x and y satisfying the following conditions.

  • 1 \leq x \lt y \leq N
  • In every tournament, at least one of players x and y advanced to the final.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M  
A_1 B_1  
A_2 B_2  
\vdots  
A_M B_M

Output

Output the answer in one line.

Sample Input 1

5 5
1 2
3 4
1 3
2 3
2 5

Sample Output 1

1

The conditions are satisfied when (x,y)=(2,3), and not satisfied otherwise.
For example, in the fourth tournament, neither player 1 nor player 4 advanced to the final, so (x,y)=(1,4) does not satisfy the conditions.

Sample Input 2

7 8
2 4
1 3
1 7
1 3
1 2
1 6
1 5
1 3

Sample Output 2

2

There are two pairs (x,y) satisfying the conditions: (1,2) and (1,4).

Sample Input 3

5 8
1 2
2 4
1 3
1 3
1 2
1 2
1 5
1 2

Sample Output 3

2