{"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$ segments that connect two of these vertices: the $i$\\-th segment connects $(a_i, 0)$ and $(b_i, 1)$.\nConsider 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$.\n\n## Constraints\n\n*   $1\\leq N, M \\leq 2\\times 10^5$\n*   $1\\leq a_i, b_i\\leq N$\n*   $a_i\\neq a_j$ or $b_i\\neq b_j$, if $i\\neq j$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc126_b","tags":[],"sample_group":[["3 3\n1 2\n2 3\n3 1","2\n\nOne optimal solution is to choose the first and second segments.\nThe first and third segments, for example, contain the same point $\\left(\\frac53, \\frac23\\right)$, so we cannot choose them both.\n![image](https://img.atcoder.jp/arc126/3e4cb12392855ea49b7ed0b643ebd370.png)"],["3 5\n1 1\n2 1\n2 2\n3 2\n3 3","3\n\nOne optimal solution is to choose the first, third, and fifth segments.\nThe first and second segments, for example, contain the same point $(1, 1)$, so we cannot choose them both.\n![image](https://img.atcoder.jp/arc126/416681cace776c87fac353e0acb9c4a1.png)"],["7 5\n1 7\n7 1\n3 4\n2 6\n5 2","1\n\n![image](https://img.atcoder.jp/arc126/2436c39ccc0fa35fc57d35647bce9f08.png)"]],"created_at":"2026-03-03 11:01:14"}}