← 返回题目列表

Codeforces · 159/B

B. 媒婆

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

Polycarpus 有 n 个标记和 m 个标记帽。每个标记由两个数字描述:xi 是颜色,yi 是直径。相应地,每个盖子由两个数字描述:aj 是颜色,bj 是直径。 Cap(aj,bj)只有在直径匹配时才能闭合标记(xi,yi),即bj = yi。此外,如果帽子颜色和标记颜色匹配,即aj = xi,则标记被认为是完美闭合的。

找到关闭最大标记数的方法。如果有多种这样的方法,则选择具有最多数量的精美闭合标记的一种。

输入

第一个输入行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — 相应的标记数量和大写字母数量。

接下来的 n 行描述了标记。第 i 行包含两个以空格分隔的整数 xi, yi (1 ≤ xi, yi ≤ 1000) — 相应地,第 i 个标记的颜色和直径。

接下来的 m 行描述了上限。第 j 行包含两个以空格分隔的整数 aj, bj (1 ≤ aj, bj ≤ 1000) — 相应地,第 j 个盖子的颜色和直径。

输出

打印两个以空格分隔的整数 u, v,其中 u 是闭合标记的数量,v 是以寻求的最佳方式完美闭合标记的数量。请记住,您必须找到关闭最大数量标记的方法,如果有多种这样的方法,您应该选择精美闭合标记数量最多的一种。

示例

输入 #1

3 4
1 2
3 4
2 4
5 4
2 4
1 1
1 2

输出 #1

3 2

输入 #2

2 2
1 2
2 1
3 4
5 1

输出 #2

1 0

注意

在第一个测试样本中,第一个标记应由第四个盖封闭,第二个标记应由第一个盖封闭,第三个标记应由第二个盖封闭。因此,三个标记将被关闭,其中两个将被完美地关闭——第一个和第三个标记。