妨碍祭典的孩子，必须受到惩罚！

新

老师！必须在新和魍魉组毁掉神木祭之前阻止她们！在这里打起来可能会点燃烟花……所以我想请修行部的同学们帮忙，用绳子抓住新。

广场是一个 $N \times N$ 的网格。我现在位于第 $1$ 行第 $1$ 列格子的正中心，新则位于广场上某个格子的正中心。有同学们帮忙，就能从一个格子的中心移动到另一个格子的中心，一边移动一边铺设绳子。修行部的同学们只能向上下左右相邻的格子移动。

假设修行部的同学们从第 $1$ 行第 $1$ 列出发，依次经过总共 $K+1$ 个格子 $P_0$、$P_1$、$\cdots$、$P_K$。

• $P_0$ 是起点，即第 $1$ 行第 $1$ 列。
• $P_K$ 是新所在的格子。

我们将绳子的长度定义为组成它的线段数，也就是 $K$。

成功用绳子抓住新后，我必须马上拉动绳子，将它收回来。不过，绳子的拐弯越多，拉动时就越容易卡住，需要的力气也越大。太费力就会拖慢回收，期间新可能逃走，情况也可能变得更危险，所以总共需要的力气也要尽量小。

当绳子由点 $P_0$、$P_1$、$\cdots$、$P_i$ 组成时，拉动一次绳子会发生以下过程。

• 移除端点 $P_i$，剩下的点 $P_0$、$P_1$、、 构成绳子。

我需要不断重复这个过程，直到只剩点 $P_0$，把整条绳子全部收回来。

必须在魍魉组做出什么事之前，尽快抓住新。因此，我会先让抓住新时绳子的长度最小，再在所有最短的绳子中，让完全回收绳子所需的总力气最小。我们需要找出能使这两个值最小的修行部同学们的移动方式。老师，您能帮帮我吗？

海香一定只出现在第 $1$ 行第 $1$ 列，新所在的格子恰好有一个。

保证一定能够抓住新。

时间限制

2000 ms

内存限制

256 MB

检查器

CUSTOM