分数: 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
