[WF2013]Up a Tree

Anatoly Cheng McDougal 在许多方面都是一个典型的新生。如果可以，他会尝试将代码剪切和粘贴从而替代从头写一段代码。显然，这种方法会无法避免地给他带来一些问题。例如，当他第一次学习树的先序，中序和后序遍历后，就写下了一段树的先序遍历的代码（如左下角所示），随后，他简单的剪切和粘贴的这段代码，然后将输出语句调整到正确的位置，并将过程（函数）重命名。但是，他忘记重新书写将会在内部被调用的过程（函数）名，从而导致生成了如下有问题的树的先序，中序和后序遍历代码。

void prePrint(TNode t)

{

output(t.value);

if (t.left != null)

prePrint(t.left);

if (t.right != null)

prePrint(t.right);

}

void inPrint(TNode t)

{

if (t.left != null)

prePrint(t.left);

output(t.value);

if (t.right != null)

prePrint(t.right);

}

void postPrint(TNode t)

{

if (t.left != null)

prePrint(t.left);

if (t.right != null)

prePrint(t.right);

output(t.value);

}

译者注 prePrint 先序遍历过程（函数），inPrint 中序遍历过程（函数），postPrint 后序遍历过程（函数），TNode 树结点类型，left 左儿子，right 右儿子，null 空结点，output 输出，void 空类型，if 条件语句标志。

此时，Anatoly 表现得不再像一个新生。他其实就测试了自己的代码！不幸地，当输出的结果不正确时，他又变回了新生样。他紧张起来，随即开始随机地改变三个过程中的调用，希望这能奏效。显然，情况更糟了。

Anatoly 的教授用一个随机的字符树测试了这段代码。当她看到了这段程序的输出之时，她已经正确地猜到了刚才发生的事情。但是，她并不想直接地浏览他的代码，相反地，她决定仅仅通过观察程序的输出，来重构 Anatoly 的代码。为了做到这一点，她正确地做了如下的假设：

1. 输出语句在各个过程（函数）已经在正确的位置。（例如，在中序遍历中，输出语句在两个递归调用中间）。

2. 在涉及到这三个过程（函数）的六次递归调用中，恰好有两个调用为先序遍历 (prePrint)，恰好两次为中序遍历 (inPrint)，还有恰好两次为后序遍历 (postPrint)，虽然有可能在错误的过程（函数）里。

不久教授就觉察到，从他的输出中，重构 Anatoly 的代码和测试数据并非易事，而且结果可能是多元的。你需要帮助他重构出所有可能的 Anatoly 的代码。另外，对于所有这样的重构，请您找到能够产生这种输出的，字典序最小的树（将会在输出中详述）。

输入只有一个测试点，各点在三行分别有三个字符串：对于某棵树，Anatoly 的先序，中序和后序遍历的输出（和描述保持相同的顺序）。

每个字符串包含 n 个大写字母 （4 ≤ n ≤ 26），且无分隔。数据保证有解。

对于测试点，输出所有可能的重构，以如下方式排序。

输出中，各个重构分为两部分。第一部分为单独一行描述 Anatoly 的代码: 先是两个 Anatoly 的先序遍历中的（递归）调用，随即是中序遍历中的（递归）调用，最后是后序遍历中的（递归）调用。调用用 Pre, In 和 Post 描述，空格隔开。例如，若 Anatoly 的代码正确，那么重构的输出应该是 Pre Pre In In Post Post。

第二部分包括三行描述会产生观察到的输出的输入数据。第一行为正确的先序遍历，第二行为正确的中序遍历，第三行为正确的后序遍历。

字典序最小的树拥有字典序最小的先序遍历。如果答案仍然多元，字典序最小的树为这当中拥有字典序最小的中序遍历的树。

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH