2446. [HZOI 2016]水母

【题目描述】

水母与树有着密切的联系，水母的很多性质可以由树拓展而得，水母的很多问题可以由断链后的树解决。

   某天，小TLE正在研究水母，突然他有了一个疑问：水母的深度是什么？

   这个问题对小TLE来说太难了！！因为他并不能确定谁是水母的根！！

   于是小TLE找到了CE学长，CE学长：你先去解决这道与深度有关的问题，我再教你这道题！

CE学长的问题是这样的：

     已知一个有n个结点的树的dfs序和bfs序，求其可能的深度的范围。

小TLE当然不会这个问题了，于是他又找到了你：小RE！

【输入格式】

第一行一个整数n

接下来一行n个整数表示dfs[i]

接下来一行n个整数表示bfs[i]

【输出格式】

【样例输入】

5



1 2 4 5 3



1 2 3 4 5

【样例输出】

3 4

【提示】

  样例解释：

数据范围：

对于20%的数据n<=10

对于40%的数据n<=100

对于60%的数据n<=2000

对于80%的数据n<=1000,000

对于100%的数据n<=10,000,000

数据保证存在一棵合法的树同时满足dfs序和bfs序。

对于树中任意的三个节点a,b,fa,如果a,b都是fa的儿子，则a,b在bfs序中和dfs序中的相对前后位置是一致的。

您可能需要[快读代码]:

int read()
{	
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int x=0; 
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar(); 
	return x;
}

您可能需要[开栈代码]：

        int __size__=32<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));

【来源】

一只名字很长的蒟蒻。