You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个边长为 $n$ 的正三角形可以被划分成 $n^2$ 个小的边长为 $1$ 的正三角形，称为单位三角形。边长为 $3$ 的正三角形被分成三层共 $9$ 个小的正三角形，我们把它们从顶到底，从左到右以 $1\sim 9$ 编号，见下图。

四个这样的边长为 $n$ 的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序（从顶向底视角）编号为 $A,B,C$，底面编号为 $D$。侧面的 $A,B,C$ 号三角形以三棱锥的顶点为顶，底面的 $D$ 号三角形以它与 $A,B$ 三角形的交点为顶。

其中 $\tt .$ 表示这个三角形面的 $1$ 号三角形位置，并依次编号下去。

上图为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面 $A,B,C$ 分别向纸内方向折叠即可还原成三棱锥。我们把这 $A,B,C,D$ 四个面各自划分成 $n^2$ 个单位三角形。

对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形。显然，每个单位三角形有三个相邻的单位三角形。现在，把 $1\sim 4n^2$ 里的所有整数分别随机填入四个面总共 $4n^2$ 个单位三角形中。

现在要求你编程求由单位三角形组成的最大二叉搜索树。所谓最大二叉搜索树，是指在所有由单位三角形组成的二叉搜索树中节点最多的一棵树。要求当 $i$ 作为二叉搜索树的一个节点时，$i$ 的儿子（如果有的话）和 $i$ 的父亲（如果有的话）必须与 $i$ 有邻边（三棱锥状态下的邻边，而非展开图的邻边）。

一棵二叉搜索树满足这个节点的左子树得每个值全部小于这个节点，这个节点的右子树的每个值全部大于这个节点。

输入格式

输入的第一行为一个整数 $n$，表示展开图中每个面的三角形边长，也就是这个面有 $n^2$ 个单位三角形。

接下来每行 $n^2$ 个整数，一共四行，第一行表示 $A$ 面的单位三角形中填入的数，第二行表示 $B$ 面，以此类推。

输出格式

输出仅一行一个整数，表示最大二叉搜索树的节点个数。

3 
19 33 32 31 29 3 5 4 30 
22 25 20 21 12 24 23 34 35 
14 13 15 26 18 17 8 16 27 
11 10 9 1 28 7 2 6 36

17

提示

样例解释

以下以 $A$ 面为例。记 $f(A,x)$ 表示 $A$ 面的第 $x$ 个单位三角形，以此类推。

$f(A,9)$ 与 $f(D,1)$ 有邻边，$f(A,7)$ 与 $f(D,2)$ 有邻边，$f(A,5)$ 与 $f(D,5)$ 有邻边。

$f(A,1)$ 与 $f(B,1)$ 有邻边，$f(A,4)$ 与 $f(B,2)$ 有邻边，$f(A,9)$ 与 $f(B,5)$ 有邻边。

$f(A,1)$ 与 $f(C,1)$ 有邻边，$f(A,2)$ 与 $f(C,4)$ 有邻边，$f(A,5)$ 与 $f(C,9)$ 有邻边。

以数字 $1$ 为二叉搜索树的根，可以得到节点最多的二叉搜索树为：

数据范围

对于 $100\%$ 的数据，$1\leqslant n\leqslant 18$，保证四个面所有单位三角形上填入的数互不相同且都取自 $[1,4n^2]$。