Description

Keke and Kaka drew a huge $N*N$ chessboard. They want to place as many international chess rooks as possible on this board so that none of them can attack each other (a rook can attack along rows and columns).

But the answer is obviously the board width $N$, so Keke restricts that pieces can only be placed on a finite set of $M$ positions on the board. (Other positions cannot hold pieces, but rooks can still pass through them to attack other pieces.) However, this does not stump the two smart kids; they quickly figure out that the answer is $K$.

Then Kaka raises another question: If we remove one position from these $M$ allowed positions while still ensuring that at most $K$ rooks can be placed (i.e., the maximum remains $K$), how many feasible choices are there?

[Task] Write a program to:

• Read from the input file the size of the board and the positions on the board where pieces can be placed.
• Compute the number of feasible choices as Kaka described.
• Output your answer.

Input Format

The first line contains two positive integers $N$ and $M$, representing the size of the board and the number of positions where pieces can be placed.

The following $M$ lines each describe one position with two integers $x_i$ and $y_i$, indicating that this position is at row $x_i$, column $y_i$ of the board.

The same position will not be described twice.

Output Format

The output contains a single integer, representing the number of feasible choices.

3 4
1 2
1 3
2 2
2 1

4

Hint

For all testdata, it is guaranteed that: $1\le i \le M\le 6\times 10^5,1\le x_i,y_i\le N\le 2\times 10^5$.

Translated by ChatGPT 5