{"problem":{"name":"Islands War","description":{"content":"There are $N$ islands lining up from west to east, connected by $N-1$ bridges. The $i$\\-th bridge connects the $i$\\-th island from the west and the $(i+1)$\\-th island from the west. One day, disputes ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc103_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc103_d","tags":[],"sample_group":[["5 2\n1 4\n2 5","1\n\nThe requests can be met by removing the bridge connecting the second and third islands from the west."],["9 5\n1 8\n2 7\n3 5\n4 6\n7 9","2"],["5 10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n4 5","4"]],"created_at":"2026-03-03 11:01:14"}}