史莱姆与询问

英文题名：H. Slime and Queries
来源：Codeforces 2237H
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：5 seconds
空间限制：1024 megabytes

题目描述

树上有一个占据 $m$ 个连通点的史莱姆。它可以移动占据集合但必须保持连通，也可以按顺序吃掉出现的食物。询问被在线编码，要求输出每个前缀食物序列的最少移动次数。

输入格式

第一行输入 $t$。每组输入 $n,m,q$、树边、初始占据点和 $q$ 个编码询问。

输出格式

每组输出 $q$ 个答案。

样例

10
5 2 3
3 5
2 1
4 3
3 2
1 2
1 4 3
6 3 4
5 1
1 3
6 1
4 1
2 1
1 2 3
5 2 5 6
7 3 5
3 7
4 2
1 3
2 1
6 3
5 2
1 2 4
7 3 2 5 2
5 2 5
3 1
1 5
2 1
4 1
1 2
3 3 3 4 2
6 3 6
4 6
3 2
1 2
5 4
2 4
2 4 5
6 6 1 2 4 6
7 4 5
5 2
3 1
2 1
3 7
6 3
4 2
1 2 3 4
7 4 4 5 1
4 3 4
3 1
1 4
2 1
1 2 3
4 1 2 3
6 2 5
2 4
5 4
2 1
6 4
3 2
1 2
6 1 1 1 2
7 2 5
2 4
7 3
3 6
1 3
1 2
5 2
1 2
4 6 1 6 5
8 4 6
5 2
3 2
7 5
4 3
8 7
1 2
6 5
2 3 4 5
8 7 3 3 7 8

0 2 3
1 1 2 3
2 4 6 8 9
1 2 3 4 4
1 2 3 4 4 4
1 2 3 3 4
1 1 2 2
2 4 6 8 9
1 4 7 10 11
2 3 4 4 5 5