← 返回题目列表

Codeforces · 398/B

B. 粉刷墙壁

中文机器翻译题面 查看原题

用户 ainta 决定粉刷墙壁。墙由 n2 个瓷砖组成,排列在 n × n 的桌子中。有些瓷砖是涂漆的,有些则没有。因为他想把它画得漂亮,所以他会遵循以下规则。

1. 首先用户 ainta 看向墙壁。如果每一行上至少有一个已着色的单元格以及每一列上至少有一个已着色的单元格,则他停止着色。否则,他将转到步骤 2。
2. 用户不能以均匀的概率选择墙上的任何瓷砖。
3. 如果他选择的图块没有被涂漆,他会对该图块进行涂漆。否则,他会忽略它。
4. 然后,即使他不刷瓷砖,他也会休息一分钟。然后 ainta 转到步骤 1。

然而,ainta 担心完成这项工作是否会花费太多时间。所以他想通过上面的方法计算出粉刷墙壁所需的预计时间。帮助他找到预计的时间。您可以假设选择和绘制任何瓷砖根本不花费任何时间。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 2·103; 0 ≤ m ≤ min(n2, 2·104)) — 墙的大小和绘制单元格的数量。

接下来 m 行,每行包含两个整数 ri 和 ci (1 ≤ ri, ci ≤ n) — 绘制单元格的位置。保证位置都是不同的。考虑表的行从 1 到 n 编号。考虑表的列从 1 到 n 编号。

输出

在一行中打印粉刷墙壁的预计时间(以分钟为单位)。如果绝对或相对误差最多为 10 - 4 个,您的答案将被视为正确。

示例

输入 #1

5 2
2 3
4 1

输出 #1

11.7669491886

输入 #2

2 2
1 1
1 2

输出 #2

2.0000000000

输入 #3

1 1
1 1

输出 #3

0.0000000000