题目描述

小P最近在玩Civilization V，游戏的地图是一棵树，树的每个节点都可以当作战场，刚开始每个节点的战斗加成为$0$

现在小P拥有两种人员：

一种是工人，每个工人会有一个起点$u$和终点$v$，工人可以使$u->v$路径上每个节点的战斗加成$+1$

一种是骑兵，每个骑兵也有一个起点$u$和终点$v$，骑兵可以选择$u->v$路径上任意节点战斗

现有$m$个工人和$q$个骑兵，问每个骑兵作战最多可以拥有多少战斗加成

输入格式

第一行三个整数$n,m,q$

接下来一行$n-1$个数，第$i$个数$f_i$表示第$i+1$个节点的父亲

接下来$m$行，每行两个整数$u,v$，表示一个工人

接下来$q$行，每行两个整数$u,v$，表示一个骑兵

输出格式

$q$行，对于每个骑兵，输出他作战最多可以拥有多少战斗加成

样例

样例输入1

5 5 5
1 1 1 4 
4 5
4 1
4 3
5 3
4 5
1 3
3 5
1 1
5 2
4 2

样例输出1

3
5
3
5
5

样例输入2

9 5 5
1 2 2 4 5 3 4 6 
4 9
4 7
1 7
1 2
2 1
9 9
9 9
3 3
7 7
2 2

样例输出2

1
1
2
2
4

数据范围与提示

对于$15\%$的数据，保证$n,m,q\le 1000$

对于另外$15\%$的数据，保证$f_i=i$

对于另外$10\%$的数据，保证所有$u=v$

对于另外$10\%$的数据，保证工人的$u=v$

对于另外$10\%$的数据，保证骑兵的$u=v$

对于$100\%$的数据，保证$n,m,q\le 500,000$且$f_i\le i$