← 返回题目列表

Codeforces · 72/F

F. 油

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

石油工业国有化后,摩萨台博士想要挖一些油井来提取波斯湾的所有石油。但波斯湾面积巨大,石油储量无穷。所以摩萨台博士只在波斯湾的一个n×m大小的矩形平面上工作。这个矩形中的每个单元格要么含有无限量的油,要么什么也不含有。

两个单元格被认为是相邻的,当且仅当它们具有公共边时,路径是单元格的序列 c1, c2, ..., cx,因此它们都含有油,并且对于每个 i,ci 与 ci - 1 和 ci + 1 相邻(如果它们存在)。当且仅当两个单元之间存在路径时,它们才被视为相互连接。如果我们在某个单元中挖一口井,我们就可以从通过油路与其连接的所有单元中提取石油。不允许在空单元格上挖井。

摩萨台博士还知道,在波斯湾,空单元格形成行和列。 IE。如果某个单元格为空,则它的列完全为空,或者它的行完全为空,或者两者都是。

帮助摩萨台博士找出他需要挖多少口井才能获取该地区的所有石油。

输入

第一行有两个正整数 n 和 m (1 ≤ n, m ≤ 100)。

第二行有一个整数 t (0 ≤ t ≤ n),即空行数。接下来是 t 个不同的正整数,这些是空行的数量,并且在范围 [1, n] 内。

第二行有一个整数 s (0 ≤ s ≤ m),表示没有油的柱数。接下来是 s 个不同的正整数,这些是空列的数量,范围为 [1, m]。

请注意,行的编号从 1 到 n(从上到下),列的编号从 1 到 m(从左到右)。

输出

一个整数,摩萨台博士必须挖掘的最少井数。

这实际上是通过删除给定的行和列来查找有多少个区域。

示例

输入 #1

2 3
1 2
1 2

输出 #1

2

输入 #2

4 4
2 2 3
3 2 3 1

输出 #2

2

输入 #3

2 3
1 1
0

输出 #3

1