题目描述

在坐标平面上，我们有 $2N$ 个顶点，其 $x$ 坐标为 $1, 2, \ldots, N$，$y$ 坐标为 $0$ 或 $1$：$(1, 0),\ldots, (N,0), (1,1), \ldots, (N,1)$。有 $M$ 条线段连接其中两个顶点：第 $i$ 条线段连接 $(a_i, 0)$ 和 $(b_i, 1)$。

考虑选择其中的 $K$ 条线段，使得任意两条线段不包含相同的点。在这里，我们认为线段的两个端点都被包含在该线段内。找出 $K$ 的最大可能值。

约束条件

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 若 $i \neq j$，则 $a_i \neq a_j$ 或 $b_i \neq b_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