/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
座標平面上に、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
Score : 400 points
Problem Statement
In the coordinate plane, we have 2N vertices whose x-coordinates are 1, 2, \ldots, N and whose y-coordinates are 0 or 1: (1, 0),\ldots, (N,0), (1,1), \ldots, (N,1). There are M segments that connect two of these vertices: the i-th segment connects (a_i, 0) and (b_i, 1).
Consider choosing K of these M segments so that no two chosen segments contain the same point. Here, we consider both endpoints of a segment to be contained in that segment. Find the maximum possible value of K.
Constraints
- 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, if i\neq j.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 \vdots a_M b_M
Output
Print the maximum possible value of K.
Sample Input 1
3 3 1 2 2 3 3 1
Sample Output 1
2
One optimal solution is to choose the first and second segments.
The first and third segments, for example, contain the same point \left(\frac53, \frac23\right), so we cannot choose them both.
Sample Input 2
3 5 1 1 2 1 2 2 3 2 3 3
Sample Output 2
3
One optimal solution is to choose the first, third, and fifth segments.
The first and second segments, for example, contain the same point (1, 1), so we cannot choose them both.
Sample Input 3
7 5 1 7 7 1 3 4 2 6 5 2
Sample Output 3
1