编程题：二叉树最长匹配前后缀路径

假定二叉树结点值为不等于0的整数。我们将二叉树中以根结点为起点、非叶结点为终点的路径称为“前缀路径”，以非根结点为起点、叶结点为终点的路径称为“后缀路径”。我们称前缀路径p和后缀路径q为最长匹配前后缀路径，如果p和q满足下列条件：

（1）路径p和q同在一条以根为起点、以叶为终点的路径里；

（2）路径p和q包含的结点序列值相等；

（3）路径p和q是整个二叉树中所有满足条件（1）（2）的最长者。


例如上面二叉树中5-9-5为最长匹配前后缀路径。请编写程序找出给定二叉树的最长匹配前后缀路径。备注：如果某前缀路径和后缀路径不在同一条以根为起点以叶为终点的路径里，则它们不能匹配，例如上面二叉树中5-2-3并不匹配。


### 输入格式:

输入包含多组测试数据。第一行为整数T，表示测试数据组数。每组数据为一行整数，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。所有测试数据包含的总结点个数不超过150000，高度不超过10000。

### 输出格式:

输出为T行，表示每组数据的最长匹配前后缀路径长度，若不存在满足条件的路径，则输出-1。

### 输入样例:

in
4
1 2 3 1 2 3 1 0 0 0 0 0 0 0 0
1 2 3 4 0 0 0 1 2 0 0 0 0
1 2 0 0 3 0 4 0 0
1 1 0 0 1 0 0



### 输出样例:

out
3
1
-1
0









答案：若无答案欢迎评论