暂无测试数据。

nnk 给定一棵树，有 $n$ 个节点, 其中有 $m$ 条为标记路径。

进行 $q$ 次询问，每次询问包含 $(u, v)$，表示询问 $(u, v)$ 简单路径上有多少完整的标记路径。

输入格式

第一行三个整数分别为 $n, m, q$。

接下来 $n - 1$ 行每行两个整数 $a_i, b_i$ 表示 $a_i, b_i$ 间有一条树边。

然后 $m$ 行每行两个整数 $x_i, y_i$ 表示 $x_i, y_i$ 间的简单路径是一条标记路径。

接下来 $q$ 行每行两个整数 $u_i, v_i$ 表示询问 $u_i, v_i$ 路径上有多少个完整的标记路径。

输出格式

对于每一个询问，输出一行一个整数表示 $(u_i, v_i)$ 上有多少完整的标记路径。

数据规模与约定

保证不存在 $u = v, x = y$ 的情况

对于前 $30\%$ 的数据，保证 $1 \leq n,m,q \leq 1000$;

对于另外 $20\%$ 的数据，保证树是一条链;

对于 $100\%$ 的数据，保证 $1 \leq n,m,q \leq 10^5$。

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

1
0
2