给定一棵包含 $n$ 个节点和 $n-1$ 条边的树。两名玩家在这棵树上进行游戏。第一名玩家执红色，第二名玩家执蓝色。初始时，每名玩家恰好拥有一个自己颜色的节点。所有其他节点均为中立。玩家轮流行动，第一名玩家先手。一次移动如下：

1. 玩家选择任意一个与自己已有节点相邻的中立节点。
2. 所选节点被染成该玩家的颜色。
3. 同时，所选节点的所有属于另一名玩家的邻居节点，都会被重新染成当前行动玩家的颜色。

如果一名玩家无法移动，则跳过该回合。只要至少还有一名玩家可以移动，游戏就会继续。注意，玩家不允许主动跳过回合。

可以证明游戏最终会结束。游戏结束时，每名玩家统计自己颜色的节点数量。拥有节点数较多的一方获胜。

Adilkhan 和 Batyrkhan 玩了一段时间这个游戏。Adilkhan 是先手，Batyrkhan 是后手。在某个时刻，他们感到厌倦，于是请求你和你的朋友 Daniyar 代替他们继续游戏。你将扮演 Adilkhan，Daniyar 将扮演 Batyrkhan。同时，他们保证现在轮到 Adilkhan 行动。

Adilkhan 和 Batyrkhan 只是为了娱乐而玩，所以他们的移动并非最优。但你和你的朋友 Daniyar 决心获胜，因此你们双方都会采取最优策略。

这样的事件重复了 $q$ 个连续的日子。具体来说，Adilkhan 和 Batyrkhan 开始游戏，进行到某个未完成的状态，然后将游戏交给你们。每一天，你都会记录下游戏的最终得分。

请问你纸上记录的 $q$ 个得分分别是多少？

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示树中的节点数。

接下来 $n-1$ 行，每行包含两个整数 $(u_i, v_i)$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示树中相连的两个节点。

下一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示天数。

第 $i$ 天的游戏状态由两行给出。

第一行以一个整数 $r_i$ 开头，后跟 $r_i$ 个整数 $(p_{i,1}, \dots, p_{i,r_i})$，表示红色节点的数量及其编号 ($1 \le p_{i,j} \le n$)。

第二行以类似格式开头，包含一个整数 $b_i$，后跟 $b_i$ 个整数 $(q_{i,1}, \dots, q_{i,b_i})$，表示蓝色节点的数量及其编号 ($1 \le q_{i,j} \le n$)。

保证给定的 $r_i + b_i$ 个节点互不相同，且该状态是由 Adilkhan 和 Batyrkhan 之间的游戏过程产生的。保证所有天数的 $r_i + b_i$ 之和不超过 $3 \times 10^5$。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 场游戏的最终得分，格式为 $a : b$，其中 $a$ 对应红色节点的数量，$b$ 对应蓝色节点的数量。

子任务

在子任务 1、2、4 和 5 中，保证在所有天数中 Adilkhan 和 Batyrkhan 都没有进行任何移动。这意味着你和 Daniyar 从游戏开始时就独立进行游戏。在这些子任务中，所有天数均满足 $r_i = b_i = 1$。

样例

样例输入 1

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

样例输出 1

5:1
6:0
1:5
5:1

样例输入 2

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

样例输出 2

4:1
1:4
4:1

说明

关于第一个样例的第一天：

游戏初始状态

对于你来说，选择节点 6 进行移动是最优的。Daniyar 在他的回合必须移动到节点 2。

你移动到节点 6，Daniyar 移动到节点 2

现在你可以移动到节点 1，并从 Daniyar 手中赢回节点 2。Daniyar 将会跳过后续所有回合，直到游戏结束，因为他无法进行任何移动。

你移动到节点 1，Daniyar 跳过回合，你移动到节点 4，游戏以 5 : 1 的比分结束

在游戏中，Daniyar 也可能完全没有他颜色的节点。在这种情况下，Daniyar 将跳过所有回合，游戏将以 6 : 0 的比分结束。

关于第一个样例的第二天：

第一个样例的第二天

如果 Adilkhan 和 Batyrkhan 从顶部节点 3 和 2 开始，且 Adilkhan 在第一步选择了节点 1，则可能发生这种情况。