E. D172 二分图最大匹配匈牙利算法【二分图：最大匹配】棋盘覆盖

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P5182 棋盘覆盖

给定一个 $N$ 行 $N$ 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 $2$ 、宽度为 $1$ 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

第一行包含两个整数 $N$ 和 $t$ ，其中 $t$ 为禁止放置的格子的数量。

接下来 $t$ 行每行包含两个整数 $x$ 和 $y$ ，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

输出一个整数，表示结果。

8 0

$1 \le N \le 100$ ， $0 \le t \le 100$