题目描述

给定一棵 $n$ 个点的树，再给定 $m$ 条特殊边（每条长度都为 $1$）。保证加入这些特殊边后，没有任何一条边属于两个不同的环；保证不存在重边与三元环；可能存在自环。

小 A 和小 B 分别位于树上的两个点 $s$ 和 $t$。两人轮流走步：

• 小 B 先手；
• 每次走步可以选择不走，或沿一条边走 $1$ 的距离；
• 特殊边只有小 A 能经过；
• 两个人分别操作完当前轮后，时间过去 $1$。

小 A 希望最小化追上小 B 的时间，小 B 希望最大化该时间。

有 $q$ 次询问，每次询问给定 $s,t$，需要回答小 A 追上小 B 的时间。

输入格式

第一行输入两个数 $id$ 和 $T$，分别表示测试点编号和测试数据组数。

对于每组测试数据：

• 第一行输入 $n,m,q$，分别表示树点数、特殊边条数、询问次数；
• 接下来 $n-1$ 行：第 $i$ 行两个整数 $u_i,v_i$，表示树上一条长度为 $1$ 的边；
• 接下来 $m$ 行：第 $i$ 行两个整数 $u'_i,v'_i$，表示一条长度为 $1$ 的特殊边；
• 接下来 $q$ 行：每行两个整数 $s,t$ 表示一次询问。

输出格式

输出若干行答案（按输入顺序），每个询问输出一行整数。

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

3
3
3
2
3

数据范围与提示

对于所有数据，保证：$1\le id\le 20$，$1\le T\le 100$，$1\le \sum n\le 2\times 10^5$，$1\le q\le 200$，且 $1\le u_i,v_i,u'_i,v'_i,s,t\le n$。保证不存在重边和三元环，可能存在自环。