← 返回题目列表

AtCoder · arc126_b

B. 交叉自由匹配

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

分数: 400 点

问题陈述

在坐标平面上,我们有 2N 顶点,其 x- 坐标是 1, 2, \ldots, N 和谁 y- 坐标是 0 or 1: (1, 0),\ldots, (N,0), (1,1), \ldots, (N,1)。 有 M 连接这些顶点中的两个顶点的线段: i第段连接 (a_i, 0) 和 (b_i, 1).

考虑选择 K 其中 M 段,以便没有两个选定的段包含相同的点。在这里,我们认为段的两个端点都包含在该段中。找出最大可能值 K.

约束

  • 1\leq N, M \leq 2\times 10^5
  • 1\leq a_i, b_i\leq N
  • a_i\neq a_j or b_i\neq b_j,如果 i\neq j.

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1
\vdots
a_M b_M

输出

打印最大可能值 K.


示例输入 1

3 3
1 2
2 3
3 1

示例输出 1

2

一个最佳解决方案是选择第一段和第二段。

例如,第一段和第三段包含相同的点 \left(\frac53, \frac23\right),所以我们不能同时选择它们。


示例输入 2

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

示例输出 2

3

一个最佳解决方案是选择第一、第三和第五段。

例如,第一段和第二段包含相同的点 (1, 1),所以我们不能同时选择它们。


示例输入 3

7 5
1 7
7 1
3 4
2 6
5 2

示例输出 3

1