{"raw_statement":[{"iden":"problem statement","content":"There are $N$ islands lining up from west to east, connected by $N-1$ bridges.\nThe $i$\\-th bridge connects the $i$\\-th island from the west and the $(i+1)$\\-th island from the west.\nOne day, disputes took place between some islands, and there were $M$ requests from the inhabitants of the islands:\nRequest $i$: A dispute took place between the $a_i$\\-th island from the west and the $b_i$\\-th island from the west. Please make traveling between these islands with bridges impossible.\nYou decided to remove some bridges to meet all these $M$ requests.\nFind the minimum number of bridges that must be removed."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq a_i < b_i \\leq N$\n*   All pairs $(a_i, b_i)$ are distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$:$\n$a_M$ $b_M$"},{"iden":"sample input 1","content":"5 2\n1 4\n2 5"},{"iden":"sample output 1","content":"1\n\nThe requests can be met by removing the bridge connecting the second and third islands from the west."},{"iden":"sample input 2","content":"9 5\n1 8\n2 7\n3 5\n4 6\n7 9"},{"iden":"sample output 2","content":"2"},{"iden":"sample input 3","content":"5 10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n4 5"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}