Rook Placement on a Constrained Chessboard

On an N × N chessboard, only M positions are allowed for placing rooks. A rook can attack any piece in the same row or column (even if there is a gap in between; note that even a forbidden cell can be passed through by a rook’s attack).

The maximum number of non‐attacking rooks that can be placed on these allowed positions is K (this value can be computed, and you may assume the smart kids already figured out that it equals K). Now, consider the following problem: if exactly one allowed position is removed (i.e. cannot be used to place a rook) but the maximum number of rooks you can place on the remaining allowed positions is still K, how many ways are there to choose such a position to remove?

You are given the chessboard size as well as the M allowed positions. Your task is to calculate the number of allowed positions that can be removed without reducing the maximum number of non‐attacking rooks that can be placed. For the purpose of this problem, the maximum number of rooks is exactly the maximum bipartite matching in the bipartite graph constructed by connecting the row and column indices for each allowed cell. In mathematical terms, if we define a bipartite graph \( G = (U, V, E) \) where \( U \) is the set of row indices, \( V \) is the set of column indices, and there is an edge \( (u, v) \in E \) if the cell \( (u, v) \) is an allowed position, then the maximum number of non‐attacking rooks is given by \[ K = \text{maximum matching}(G)\]

Your program should count, over all the M allowed positions, how many of them, when removed, will still yield a graph whose maximum matching is \( K \).

inputFormat

The first line contains two integers N and M separated by spaces.

The following M lines each contain two integers, representing the row and column indices (1-indexed) of an allowed position.

You may assume that all input integers are positive and that there are no duplicate allowed positions.

outputFormat

Output a single integer: the number of ways (i.e. the number of allowed positions) such that if that position is removed (all other allowed positions remain), the maximum number of non‐attacking rooks that can be placed is still K.

sample

3 4
1 1
1 2
2 2
3 3

1