問題文

座標平面上に、$x$ 座標が $1, 2, \\ldots, N$、$y$ 座標が $0$ または $1$ であるような合計 $2N$ 個の頂点 $(1, 0),\\ldots, (N,0), (1,1), \\ldots, (N,1)$ があります。 これらのうちの $2$ 頂点を結ぶ線分が $M$ 個あり、$i$ 番目の線分は $(a_i, 0)$ と $(b_i, 1)$ を結んでいます。

これら $M$ 個の線分から $K$ 個の線分を選び、選んだ線分のうちどの $2$ 個の線分も同一の点を含まないようにすることを考えます。ただし、線分の両端点も線分に含まれる点として扱います。可能な $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

$1, 2$ 番目の線分を選ぶことが、最適解のひとつです。

例えば $1$ 番目の線分と $3$ 番目の線分は同一の点 $\\left(\\frac53, \\frac23\\right)$ を含むため、同時に選ぶことはできません。

入力例 2

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

出力例 2

3

$1, 3, 5$ 番目の線分を選ぶことが、最適解のひとつです。

例えば $1$ 番目の線分と $2$ 番目の線分は同一の点 $(1, 1)$ を含むため、同時に選ぶことはできません。

入力例 3

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

出力例 3

1