201261: [AtCoder]ARC126 B - Cross-free Matching

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

有 $2N$ 个点 $(1,0),(2,0),\dots,(N,0),(1,1),(2,1),\dots,(N,1)$ 以及 $M$ 条边,第 $i$ 条边连接 $(a_i,0),(b_i,1)$,问这些边中有多少条边互相不相交。

加入题单

上一题 下一题 算法标签: