二叉树自动机（困难版）

题目背景

星际档案馆中保存着大量形态各异的二叉树。工程师希望制造一台结构极其简单的巡检机器人：它只有有限个内部状态，只能沿父子边移动，但可以在经过的结点上读写少量布尔标记。

你的任务是为这台机器人编写一份通用程序。无论评测器交给它哪一棵指定规模的二叉树，它都必须找到树中深度最大的全部结点，并且不能把任何其他结点误判为最深结点。

题目描述

考虑一棵有根有序二叉树。每个结点至多有一个左儿子和一个右儿子。

每个结点中保存 $26$ 个布尔变量，称为标志位，依次用小写字母 a 到 z 表示。

其中 l、r、p 三个标志位具有特殊的初始含义：

• 当且仅当当前结点存在左儿子时，l 初始为真；
• 当且仅当当前结点存在右儿子时，r 初始为真；
• 当且仅当当前结点存在父亲时，p 初始为真。

其余标志位初始均为假。所有标志位都可读写，但通常不建议修改 l、r、p。

自动机具有有限个状态，并从树根开始运行。自动机程序由一个初始状态名和若干条指令组成。

每条指令的格式为：

current_state:conditions:new_state:toggle:move

五个字段之间恰好由四个半角冒号 : 分隔，各字段含义如下。

• current_state：执行该指令前的状态名；
• conditions：需要同时满足的条件序列；
• new_state：执行该指令后进入的状态名；
• toggle：需要翻转的标志位序列；
• move：移动方向。

状态名必须由 $1$ 到 $10$ 个英文字母或数字组成。

conditions 中的每个字符表示一个条件：

• 小写字母 c 表示当前结点的标志位 c 必须为真；
• 大写字母 C 表示当前结点的标志位 c 必须为假。

同一个条件字符不能重复，但一条指令可以同时包含形如 yY 的互相矛盾条件；这种指令永远不会被执行。

toggle 只能包含互不相同的小写字母。执行指令时，其中列出的每个标志位都会翻转：真变为假，假变为真。

move 只能是以下四种之一：

• 空串：停留在当前结点；
• l：移动到左儿子；
• r：移动到右儿子；
• p：移动到父亲。

自动机的执行方式

自动机最初位于树根，状态为你输出的初始状态。

每一步中，按输出顺序寻找第一条同时满足以下条件的指令：

1. current_state 等于自动机当前状态；
2. conditions 中的全部条件均成立。

找到后，依次执行：

1. 将状态改为 new_state；
2. 翻转 toggle 中列出的标志位；
3. 按照 move 移动。

若没有任何指令可以执行，程序终止。

若自动机试图移动到不存在的结点，程序也立即终止；这条导致非法移动的指令仍计入执行步数，其状态修改和标志位翻转仍然生效。

目标

对于评测器选择的每一棵恰有 $N$ 个结点的二叉树，程序终止时必须满足：

• 所有深度最大的结点，其 x 标志位均为真；
• 所有其他结点，其 x 标志位均为假。

根结点深度为 $0$。

你可以针对不同的 $N$ 输出不同程序，也可以对所有 $N$ 输出同一份通用程序。

程序限制

输出的自动机程序必须同时满足：

• 指令条数不超过 $500$；
• 所有指令字符串的字符总数不超过 $6500$；
• 对任意不超过 $30$ 个结点的测试树，执行步数不超过 $20000$；
• 对任意不超过 $60000$ 个结点的测试树，执行步数不超过 $200000000$；
• 所有状态名长度均为 $1$ 到 $10$，且只包含英文字母或数字；
• 每条指令均符合上述语法。

输入格式

输入一行一个整数 $N$，表示评测器使用的二叉树结点数。

输出格式

第一行输出一个整数 $M$，表示接下来输出的字符串数量。

接下来输出 $M$ 行：

• 第 $1$ 行是自动机的初始状态名；
• 第 $2$ 到第 $M$ 行各是一条自动机指令，指令顺序即为执行时的优先级顺序。

因此，指令条数为 $M-1$。

本题允许多种正确输出。评测器会解析并模拟你输出的自动机，而不是将其与标准输出逐字比较。

样例 1

1

2
start
start::finish:x:

样例 1 说明

树只有一个结点。自动机执行唯一一条指令，将根结点的 x 标志位翻转为真，然后终止。

样例 2

2

6
start
start:yY:explode::r
start:l:start::l
start:r:start::r
start::finish:x:
Hello47::Hello42::

样例 2 说明

含两个结点的有根二叉树只有两种：唯一的儿子是左儿子，或唯一的儿子是右儿子。程序沿存在的儿子边走到叶子，再将叶子的 x 标志位置为真。

start:yY:explode::r 的条件互相矛盾，因此永远不会执行；最后一条指令也永远不可达，它们用于展示语法允许但不影响结果的写法。

样例 3

3

75
init
init::isdone:x:
notdone:bp:notdone:ab:p
notdone:bP:spread:ab:
notdone:ar:notdone:b:r
notdone:aR:notdone:b:
notdone:l:notdone:a:l
notdone:L:notdone:a:
isdone:xl:notdone::
isdone:xr:notdone::
isdone:bp:isdone:ab:p
isdone:bP:terminate:ab:
isdone:ar:isdone:b:r
isdone:aR:isdone:b:
isdone:l:isdone:a:l
isdone:L:isdone:a:
spread:bp:spread:ab:p
spread:bP:reduce0:ab:
spread:ar:spread:b:r
spread:aR:spread:b:
spread:lx:color:ay:l
spread:Lx:color:ay:
spread:l:spread:a:l
spread:L:spread:a:
color:X:color:x:
color:ybp:spread:yab:p
color:ybP:reduce0:yab:
color:bp:color:ab:p
color:ar:color:b:r
color:aR:color:b:
color:l:color:a:l
color:L:color:a:
reduce1:y:reduce0::
reduce0:z:reduce1::
reduce0:x:reduce0:xy:
reduce0:ybp:reduce0:aby:p
reduce0:ybP:uniq0:aby:
reduce0:bp:reduce0:ab:p
reduce0:bP:uniq0:ab:
reduce0:yar:reduce1:b:r
reduce0:ar:reduce0:b:r
reduce0:aR:reduce0:b:
reduce0:yl:reduce1:a:l
reduce0:l:reduce0:a:l
reduce0:L:reduce0:a:
reduce1:x:reduce1:xz:
reduce1:zbp:reduce1:abxz:p
reduce1:bp:reduce1:ab:p
reduce1:zar:reduce0:b:r
reduce1:ar:reduce1:b:r
reduce1:aR:reduce1:b:
reduce1:zl:reduce0:a:l
reduce1:l:reduce1:a:l
reduce1:L:reduce1:a:
uniq2:y:uniq2:xy:
uniq2:bp:uniq2:ab:p
uniq2:bP:reduce0:ab:
uniq2:ar:uniq2:b:r
uniq2:aR:uniq2:b:
uniq2:l:uniq2:a:l
uniq2:L:uniq2:a:
uniq1:x:uniq2::
uniq1:ybp:uniq0:abxy:p
uniq1:bp:uniq1:ab:p
uniq1:ar:uniq1:b:r
uniq1:aR:uniq1:b:
uniq1:l:uniq1:a:l
uniq1:L:uniq1:a:
uniq0:x:uniq1:xy:
uniq0:bp:uniq0:ab:p
uniq0:bP:isdone:ab:
uniq0:ar:uniq0:b:r
uniq0:aR:uniq0:b:
uniq0:l:uniq0:a:l
uniq0:L:uniq0:a:

样例 3 说明

这是一份适用于任意正整数 $N$ 的通用自动机程序。原页面中 $N=3,4,\ldots,30$ 的示例均返回这份相同程序。

数据范围

原页面正式示例满足：

$$1\le N\le 30.$$

附加系统测试满足：

$$1\le N\le 60000.$$

判定说明

本题是多解构造题，必须使用自定义判定器。判定器至少需要完成：

1. 检查输出格式、状态名、条件、翻转串、移动字段及长度限制；
2. 检查指令数与总字符数限制；
3. 在评测器选定的若干棵 $N$ 个结点的二叉树上模拟自动机；
4. 检查执行步数限制；
5. 检查终止时恰好所有最深结点的 x 标志位为真。