混乱的二叉树遍历（PreInPost）

题目背景

Antonio 刚刚学会二叉树的先序、中序和后序遍历，便写了一个“万能遍历函数”。然而，他在递归进入左右子树时把遍历模式传错了：当前按先序访问，左子树却可能继续使用中序；当前按后序访问，右子树又可能改成先序。

现在，我们只保留了同一棵树在两种初始模式下产生的遍历序列。请判断这些记录是否自洽；若自洽，还要补出第三种初始模式下可能得到的遍历序列。

题目描述

一棵有序二叉树共有 $n$ 个结点，结点编号为 $1,2,\ldots,n$，每个编号恰好出现一次。每个结点都有左儿子和右儿子，二者均可以为空。

遍历模式共有三种：

• pre：先访问根，再递归遍历左子树和右子树；
• in：先递归遍历左子树，再访问根，最后递归遍历右子树；
• post：先递归遍历左子树和右子树，最后访问根。

Antonio 编写的函数如下：

order(v, mode):
    if v is None:
        return []

    if mode == "pre":
        return [v.label]
             + order(v.left,  s[0])
             + order(v.right, s[1])

    if mode == "in":
        return order(v.left,  s[2])
             + [v.label]
             + order(v.right, s[3])

    if mode == "post":
        return order(v.left,  s[4])
             + order(v.right, s[5])
             + [v.label]

其中，$s$ 是一个长度为 $6$ 的模式数组。保证：

• $s_0,s_2,s_4$ 恰好是 pre、in、post 的一个排列；
• $s_1,s_3,s_5$ 也恰好是 pre、in、post 的一个排列。

给定两个不同的初始模式 $e_1,e_2$，以及两个长度为 $n$ 的排列 $a_1,a_2$。它们声称分别满足：

a1 = order(root, e1)
a2 = order(root, e2)

请判断是否存在一棵有序二叉树，使上述两式同时成立。

• 若不存在，输出 0；
• 若存在，设 $e_3$ 是 pre、in、post 中除 $e_1,e_2$ 外的第三种模式，请输出任意一份可能的 order(root, e3)。

合法答案可能不唯一，本题采用 Special Judge。

输入格式

第一行包含 $6$ 个字符串 $s_0,s_1,\ldots,s_5$。

第二行包含一个整数 $n$。

第三行包含 $n$ 个整数，表示排列 $a_1$。

第四行包含 $n$ 个整数，表示排列 $a_2$。

第五行包含两个不同的字符串 $e_1,e_2$。

输出格式

若不存在满足条件的二叉树，输出：

0

否则，先输出一个整数 $n$，随后输出 $n$ 个整数，表示任意一份合法的第三种遍历序列。

整数之间可以用任意空白字符分隔。

样例 1

输入

post in pre post in pre
5
1 2 3 4 5
2 4 3 5 1
pre post

输出

5
2 1 3 5 4

说明

第三种初始模式为 in。该样例存在多棵符合条件的树，因此也存在其他正确输出，例如 4 2 3 1 5。

样例 2

输入

pre in in post post pre
3
1 2 3
2 3 1
post pre

输出

0

说明

不存在同时产生这两份遍历序列的有序二叉树。

样例 3

输入

pre in post pre in post
9
9 3 4 1 6 5 2 7 8
3 9 1 4 2 7 8 5 6
in post

输出

9
6 1 9 3 4 5 8 7 2

数据范围

• $1\le n\le 200$；
• $a_1,a_2$ 均为 $1$ 到 $n$ 的排列；
• $e_1,e_2\in\{\texttt{pre},\texttt{in},\texttt{post}\}$ 且 $e_1\ne e_2$；
• $s_0,s_2,s_4$ 是三种模式的一个排列；
• $s_1,s_3,s_5$ 是三种模式的一个排列。

时间与空间限制

• 时间限制：$3$ 秒；
• 空间限制：$256$ MiB。

来源

TopCoder SRM 715，Division I，Level Three：PreInPost。