問題文

NN マス,横 NN マスの合計 N2N^2 マスからなるチェス盤があります.このチェス盤のマスのうち MM 個のマスに,ルークの駒が 11 個ずつ置かれています.これら以外に駒は置かれていません.

マス目の上から xx マス,左から yy マス目をマス (x,y)(x, y) と呼ぶことにします.ii 個目のルークはマス (Ai,Bi)(A_i, B_i) に置かれています.

チェス盤のマスが次の条件をすべて満たすとき,そのマスは 安全である とします.

  • そのマスにルークが置かれていない.
  • そのマスと同じ行または同じ列にルークの駒がない.

安全であるマスの個数を求めてください.

制約

  • 入力はすべて整数
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Mmin(N2,2×105)1 \leq M \leq \min(N^2, 2 \times 10^5)
  • 1Ai,BiN1 \leq A_i, B_i \leq N
  • iji \neq j ならば,(Ai,Bi)(Aj,Bj)(A_i, B_i) \neq (A_j, B_j)

入力

N M
A_1 B_1
.
.
.
A_M B_M

出力

計算結果を一行に出力せよ。

サンプル

入力1
3 2
1 3
3 3
出力1
2

チェス盤の様子を下に図示します.駒が置かれていないマスを .,置かれているマスを * で表しています.ルークは 22 つあり,それぞれマス (1,3)(1, 3)(3,3)(3, 3) に置かれています.

..*
...
..*

安全なマスの個数は (2,1)(2, 1)(2,2)(2, 2)22 個です.

入力2
2 4
1 1
1 2
2 1
2 2
出力2
0

すべてのマスにルークが置かれています.

入力3
1000 7
45 87
13 352
700 28
548 430
123 28
700 352
723 165
出力3
989030

Submit


Go (1.21)