该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板从棺材中醒来，他不甘就此离去，他想要光宗耀祖。

于是他找来到族谱了，族谱是一个树形结构，一共有 $n$ 个结点，$n-1$ 条边，其中 $1$ 为根节点。

石老板看到族谱上有 $m$ 对黄金搭档，其中第 $i$ 对为 $(x_i,y_i)$ 。（注意顺序不能反，且可能存在重复）

石老板的脑子里突然冒出了 $q$ 个询问，每个询问都会给定树上的两个点 $a,b$ 。

他想知道在这 $m$ 对黄金搭档中，有多少对 $(x,y)$ 能满足 $x$ 是 $a$ 的祖先，且 $b$ 是 $y$ 的祖先。

注意每个点也是自己的祖先！

石老板迫切的想知道这些问题的答案，请你帮石老板完成遗愿，让他可以含笑九泉。

输入格式

第一行包含三个整数 $n, m, q$，表示树的结点数量、点对数量和询问次数。

接下来 $n−1$ 行，每行包含两个整数 $u, v$，表示树上结点 $u$ 和结点 $v$ 之间有一条边相连，不保证顺序。

接下来 $m$ 行，每行包含两个整数 $x,y$，表示每对黄金搭档。

接下来 $q$ 行，每个询问包含两个整数 $a,b$ ，表示询问的点对。

输出格式

对于每个询问，在输出一行一个整数表示答案。

样例输入

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

1 3
1 4
1 6
2 5
3 1

5 2
2 5
5 6
6 5
4 1

样例输出

2
2
1
1
4

样例解释

第 $1$ 个询问对应的点对为 $(1,3),(1,4)$；

第 $2$ 个询问对应的点对为 $(1,6),(2,5)$；

第 $3$ 个询问对应的点对为 $(1,6)$；

第 $4$ 个询问对应的点对为 $(1,6)$；

第 $5$ 个询问对应的点对为 $(1,3),(1,4),(1,6),(2,5)$。

数据范围与提示

对于 $30\%$ 的数据，满足 $n,m,q\le 3000$。

对于所有数据，满足 $n,m,q\le 500000$ ，$1\le u,v,x,y,a,b\le n$，保证输入数据构成一棵树。