{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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$."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 3\n1 2\n2 3\n3 1"},{"iden":"sample output 1","content":"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)"},{"iden":"sample input 2","content":"3 5\n1 1\n2 1\n2 2\n3 2\n3 3"},{"iden":"sample output 2","content":"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)"},{"iden":"sample input 3","content":"7 5\n1 7\n7 1\n3 4\n2 6\n5 2"},{"iden":"sample output 3","content":"1\n\n![image](https://img.atcoder.jp/arc126/2436c39ccc0fa35fc57d35647bce9f08.png)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}