4210. Sayaku，移动

【题目背景】

Sayaku 闯入了影子魔女的结界，开始讨伐影子魔女。

【题目描述】

影子魔女的结界十分奇特，是一颗完全二叉树，且完全二叉树是无限延伸的，即所有节点均有左子节点与右子节点，除了根（结界的入口）的所有节点均有父亲。

影子魔女把自己的分身使魔洒落在这个完全二叉树的一些节点上，这些节点构成一个 $n$ 个节点的连通块，保证这个连通块包含根节点，显然，这个连通块本身也是一棵二叉树。连通块上的每个节点都有影子魔女的使魔，Sayaku 到达过的地方如果有使魔，则会将其击败。如果一个地方没有使魔，Sayaku 也可以到那里去。Sayaku 也可以反复经过一个地方。

在长期的战斗中，Sayaku 丧失了大部分理智，为了防止在战斗中失控，Sayaku 必须利用自己的一台留音机来提示自己，她可以听这台留音机的命令。Sayaku 初始时将站在根上，在开始移动前，Sayaku 将向留音机录入一串指令，这串指令单个字符可以是：

向左走：提示 Sayaku 向当前节点的左儿子节点走；

向右走：提示 Sayaku 向当前节点的右儿子节点走；

向上走：提示 Sayaku 向当前节点的父亲走（若没有，则命令非法）。

录入指令后，留音机将会把指令无限复读下去。比如命令为“向左走”“向右走”，那么 Sayaku 会遵从 “向左走”“向右走”“向左走”“向右走”... 一直走下去。当 Sayaku 在这棵完全二叉树的根时，执行向上走是非法的，即你需要保证不可能出现这种情况。

现在，Sayaku 告诉了你使魔藏身的的这棵二叉树连通块的前序遍历，你需要寻找到一条尽量短的指令，使得 Sayaku 能够击败所有使魔从而击败影子魔女。

【输入格式】

一行一个字符串，由 0123 中的字符组成，表示使魔藏身的的这棵二叉树连通块的前序遍历。

0：表示这是一个没有儿子的节点。

1：表示这是一个只有左子的节点。

2：表示这是一个只有右子的节点。

3：表示这是一个既有左子又有右子的节点。

【输出格式】

一个整数，表示最短指令的长度。

【样例输入1】

1313000

【样例输出1】

3

【样例输入2】

333003003300300

【样例输出2】

15

【样例说明】

对于样例输入 1，一种可行的最短指令为 “向左走”“向右走”“向上走”。

【数据规模与约定】

注意：本题标解常数极小，保证时间限制在 std 最大点用时五倍以上。

特殊性质 $\text{A}$：给定的联通块是一颗完全二叉树，即除了叶子节点每个节点都有左儿子和右儿子。

特殊性质 $\text{B}$：满足给定的联通块只有一个叶子节点，且其他点均只有一个左儿子。

大样例，所有大样例均无特殊性质。

【来源】

luogu P5597。