SP7969 ACPC10G - A Knights’ Tale

在一个无限大的棋盘上，有 $N$ 匹骑士马，每匹马都占据在不同的格子里。在棋盘上还有 $N$ 个目标格子，这些目标格子的位置可能与骑士马的初始位置不同。你的任务是找出每个骑士马至少需要多少步才能到达各自的目标格子，并且最后每个目标格子上恰好有一匹骑士马。 骑士马的移动方式是标准的“L”形，即在一个方向上移动一格，同时在另一个方向上移动两格。在骑士马移动的过程中，允许多匹骑士马短暂地共用同一格子，但最终每匹骑士马必须各占一个不同的目标格子。

输入包含一个或多个测试用例。每个测试用例由 $2N + 1$ 行组成。 第一行是一个整数 $N$，表示骑士马和目标格子的数量（$1 \le N \le 25$）。接下来的 $N$ 行，每行有两个整数 $X_i$ 和 $Y_i$，代表第 $i$ 匹骑士马的初始坐标。之后的 $N$ 行，每行有两个整数 $A_i$ 和 $B_i$，表示第 $i$ 个目标格子的坐标。输入的最后以一个单独的零结尾。

对于每个测试用例，输出一行： k. m 其中 k 是测试用例的编号（从 1 开始），m 是实现目标所需的最少的移动步数。 **本翻译由 AI 自动生成**