CF398B Painting The Wall

用户 ainta 决定粉刷一面墙。这面墙由 $n^{2}$ 个瓷砖组成，排成一个 $n \times n$ 的矩阵。有些瓷砖已经被刷上颜色，其他的还没有。为了让墙变得美观，他将遵循以下规则： 1. 首先，ainta 观察这堵墙。如果每一行和每一列都至少有一个瓷砖已经被刷上颜色，他就停止粉刷。否则，进入第 2 步。 2. ainta 以等概率随机选择一个瓷砖。 3. 如果他选中的瓷砖还没被上色，他就将其涂色，否则忽略此次行为。 4. 无论是否成功将瓷砖涂色，他都要休息一分钟。然后 ainta 回到第 1 步。 然而，ainta 担心完成这个工作需要很长时间。所以他想计算按照以上方法粉刷完墙所需的期望时间。请帮助他求出所需的期望时间。你可以假设选择和涂色任何一个瓷砖都不消耗时间。

第一行为两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^{3}$；$0 \leq m \leq \min (n^{2}, 2 \cdot 10^{4})$）——墙的规模和现在已经被涂色的瓷砖数量。 接下来 $m$ 行，每行包含两个整数 $r_{i}$、$c_{i}$（$1 \leq r_{i}, c_{i} \leq n$）——已涂色瓷砖的位置。保证所有位置互不相同。矩阵的行从 $1$ 到 $n$ 编号；列也从 $1$ 到 $n$ 编号。

输出一个实数，表示粉刷完整面墙的期望时间（单位：分钟）。你的答案只要绝对误差或相对误差不超过 $10^{-4}$ 即被认为是正确的。

由 ChatGPT 5 翻译