{"problem":{"name":"[KMOI R1] 军事行动","description":{"content":"喵星边境局势愈发紧张，导致发生边境冲突。喵星军队总司令小袁立即对 $Y$ 星采取军事行动。 整个宇宙可以看作一个平面直角坐标系，城市 $1,2,\\dots,n$ 的坐标分别为 $(x_1,y_1),(x_2,y_2),\\dots(x_n,y_n)$。 现在小袁率领的**若干支**舰队（可以理解为小袁的军事力量是无限的）驻扎在边境要塞，城市 $1$ 处。他的舰队会进行以下移动： - 如果舰队的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9709"},"statements":[{"statement_type":"Markdown","content":"喵星边境局势愈发紧张，导致发生边境冲突。喵星军队总司令小袁立即对 $Y$ 星采取军事行动。\n\n整个宇宙可以看作一个平面直角坐标系，城市 $1,2,\\dots,n$ 的坐标分别为 $(x_1,y_1),(x_2,y_2),\\dots(x_n,y_n)$。\n\n现在小袁率领的**若干支**舰队（可以理解为小袁的军事力量是无限的）驻扎在边境要塞，城市 $1$ 处。他的舰队会进行以下移动：\n\n- 如果舰队的坐标为 $(x,y)$，那么一天之后它可以移动到 $(x-1,y+2)$ 或 $(x+1,y+2)$ 或 $(x+2,y+1)$ 或 $(x-2,y+1)$ 或 $(x-1,y-2)$ 或 $(x+1,y-2)$ 或 $(x+2,y-1)$ 或 $(x-2,y-1)$ 处。\n\n其中环绕在外的还有一条小行星带，当舰队的坐标  $(x,y)$ 且 $x\\le 0$ 或 $y\\le 0$ 或 $m < x$ 或 $m < y$ 时，舰队就会撞到小行星带。这是小袁所不想看到的。\n\n现在小袁要攻打城市 $2,3,\\dots,n$，每一次他都会从一个**已经占领**的城市（城市 $1$ 也算），派出舰队前往城市 $i$ 并攻打它，舰队**到达之后的第二天**城市 $i$ 就被攻占了。\n\n特别的，小袁在一个舰队**前往攻打或攻打一个城市**的时候不会派出另外一支舰队，在**攻占一座城市后当天**可以立即派出另外一支舰队。\n\n小袁想问，最少要花多少时间才能攻占所有的城市。\n\n**攻打顺序可以不按照 $2,3\\dots n$ 的顺序。**\n\n## Input\n\n第一行一个整数 $n,m$，表示城市个数和小行星带的范围。\n\n接下来 $n$ 行，每一行两个正整数 $(x_i,y_i)$，表示城市 $i$ 的坐标。**保证 $1\\le x_i,y_i \\le m$**。\n\n## Output\n\n一个整数 $ans$，表示最少要花的时间。\n\n[samples]\n\n## Background\n\n$$\\blue{他们来了。}$$\n\n$$\\purple{集结军队，干掉他们，一个不留。}$$\n\n$$\\blue{是！}$$\n\n## Note\n\n## 样例一解释：\n\n舰队在第一天来到了 $(3,2)$ 的位置，第二天到达了城市 $2$ 的位置，第三天占领了城市 $2$。总共花了 $3$ 天。\n\n## 样例二解释：\n\n舰队在第一天到达了城市 $2$ 的位置，第二天占领了城市 $2$。第三天到达了城市 $3$ 的位置，第四天占领了城市 $3$。总共花了 $4$ 天。\n\n## 数据范围\n\n**本题采用 Subtask 捆绑测试。**\n\n|子任务编号|  测试点编号| $n$ | $m$ |特殊性质|分值|\n|:-----:| :----------: | :----------: | :----------: | :----------: |:---:|\n|$1$| $1\\sim2$ | $1\\le n\\le 7$ |$4\\le m\\le 7$|无|$10$|\n|$2$| $3\\sim7$ | $1\\le n\\le 200$ |$4\\le m\\le 70$|无|$25$|\n|$3$| $8\\sim9$ | $1\\le n\\le 150$ |$4\\le m\\le 150$|有|$15$|\n|$4$| $10\\sim20$ | $1\\le n\\le 2000$ |$4\\le m\\le 150$|无|$50$|\n\n特殊性质：对于每一个 $1\\le i\\le n-1$，都有 $x_i = x_{i+1}$。\n\n**数据严格保证不会有不同的城市拥有相同的坐标。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9709","tags":["O2优化","广度优先搜索 BFS","生成树"],"sample_group":[["2 20\n1 1\n1 3","3"],["3 150\n1 2\n2 4\n4 3","4"],["10 10\n1 4\n2 3\n2 6\n3 6\n10 3\n1 5\n4 2\n5 3\n2 8\n9 2","23"],["查看附件的 example4.in","查看附件的 example4.out"]],"created_at":"2026-03-03 11:09:25"}}