Start: Jul, 06, 2019 10:00:00
20190706Python程序设计基础培训第四次作业(树)
End: Jul, 17, 2019 12:00:00
Time elapsed:
Time remaining:

【数据结构】二叉树任意节点距离 2170

Time Limit:  1 s      Memory Limit:   128 MB
Submission:36     AC:28     Score:1

Description

对于给定的二叉树先序遍历结果,建立二叉树。

二叉树的节点值为一个char 类型变量。

中序输入为一个字符串。

若为字母则代表当前位置有节点,且节点值为当前位置字母。

若当前位置为#,则代表当前位置没有节点。

如:

ABD#G###CE##FH###

对应一颗这样的二叉树

接下来有多组询问任意两个节点之间的距离

Input


单组输入

第一行输入为一个二叉树的先序遍历结果。

第二行为一个数字Q

接下来Q行

每次询问输入两个节点代表的字符

Output

对于每次询问,输出节点之间的距离

Samples

input
ABD#G###CE##FH### 3 A D A C D C
output
2 1 3