AtCoder Regular Contest 126
翻译中…
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$.
翻译中…
样例
Input #1
3 3
1 2
2 3
3 1
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.
Input #2
3 5
1 1
2 1
2 2
3 2
3 3
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.
Input #3
7 5
1 7
7 1
3 4
2 6
5 2
Output #3
1
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。