背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 Problem C。

原题许可协议为 CC BY-SA。

题目描述

一个著名的逻辑问题是：在一张纸上有 $9$ 个点，要求用铅笔画出 $4$ 条线段把它们连起来，并且中途不能把铅笔从纸上抬起。这个问题本身并不太难（虽然需要一些跳出框架的思考），但 Simone 最近正在围绕这个概念的推广版本制作一款名为“Connect the Dots”的游戏。

在 Connect the Dots 中，你会看到一个 $4 \times 4$ 的规则点阵。每个点被赋予 $1$ 到 $16$ 之间一个唯一的编号。任务是按照编号顺序连接这些点，从编号为 $1$ 的点开始，到编号为 $16$ 的点结束。你需要使用尽可能少的线段连接它们，从点 $1$ 开始，并且每一条线段的终点都是下一条线段的起点。

线段允许相交，也允许互相重叠。此外，在尝试连接当前目标点时，允许线段经过其他点。例如，按照 $1,4,2,3,2,4,\ldots$ 的顺序访问前几个点是可以接受的。形式化地说，序列 $1,2,\ldots,15,16$ 必须是被访问点序列的一个子序列。

:::align{center}

图 1：第一个样例的一种解法。

:::

Simone 让你尝试这个谜题，并和你赌一个气球说它太难了。写一个程序来解决这个谜题，证明她错了！

输入格式

输入包含 $4$ 行，每行 $4$ 个整数，表示点阵中各个点的编号。

第 $i$ 行第 $j$ 个数表示点阵第 $i$ 行第 $j$ 个点的编号。

输出格式

输出按顺序连接所有点所需的最少线段数量。

1 2 3 4
10 11 12 5
9 16 6 13
8 7 15 14

6

1 2 3 4
8 9 10 11
7 15 16 12
6 14 13 5

7

提示

【数据规模与约定】

输入中的 $16$ 个数字均在 $1$ 到 $16$ 之间（包含端点），并且两两不同。