#282. 1281. UVA 10410 Tree Reconstruction

1281. UVA 10410 Tree Reconstruction

#1281. UVA 10410 Tree Reconstruction

题目描述

给定一棵树,则我们就可以得到它的BFS序列和DFS序列。所谓BFS序列,就是从根节点开始扩展,深度小的优先,对同一个节点若干个儿子,编号小的优先扩展;所谓DFS序列,就是从根节点开始,深度大的优先,对同一个节点若干个儿子,编号小的优先扩展。现在的问题是,给定一棵树的BFS序列和DFS序列,请你算出有多少棵树满足条件。

输入格式

第一行包含一个整数N,表示树中节点的个数。第二行中包含N个整数,表示一棵树的BFS序列。第三行中同样包含N个整数,表示这棵树的DFS序列。我们保证输入数据至少对应了一颗树。

输出格式

仅包含一个整数,表示满足条件的树的个数。

样例

样例输入

4  

1 2 3 4  

1 2 3 4  

样例输出

4

数据范围与提示

1 ≤ N ≤ 10000