Cross-free Matching

AtCoder

IDarc126_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #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.
![image](https://img.atcoder.jp/arc126/3e4cb12392855ea49b7ed0b643ebd370.png)

Input #2

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.
![image](https://img.atcoder.jp/arc126/416681cace776c87fac353e0acb9c4a1.png)

Input #3

Output #3

1

![image](https://img.atcoder.jp/arc126/2436c39ccc0fa35fc57d35647bce9f08.png)

API Response (JSON)

{
  "problem": {
    "name": "Cross-free Matching",
    "description": {
      "content": "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$ segme",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc126_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$ segme...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments