题目描述

在一个有 $n$ 个城市的国家，有 $n−1$ 条双向道路连接这些城市，形成一棵树。你现在正在这个国家旅游，有 $m$ 条特定的道路是你一定要经过的。旅行社提供了 $k$ 条可选的旅游路线。每条路线从城市 $s_i$ 出发，并沿着最短路径到达城市 $t_i$。

你的目标是从这 $k$ 条旅游路线中选择尽可能少的路线，确保所有 $m$ 条关键道路都至少被经过一次。

请计算你需要选择的最少旅游路线数量，以及达到这个最少数量有多少种可能的方案，答案对 $998244353$ 取模。一个方案定义为你选择的旅游路线的集合。如果存在一条旅游路线在一个方案中被选择而另一个方案中没有，则认为这两个方案是不同的。

如果无法经过所有特定的道路，输出 −1。

题目保证答案在模 $998244353$ 意义下非零。

输入格式

第一行包含三个整数 $2⩽n⩽2×10^5,1⩽m⩽22,1⩽k⩽2×10^5$，分别表示城市数量、特定道路 数量和旅游路线数量。

接下来的 $n−1$ 行，每行包含两个整数 $1⩽u_i,v_i⩽n$，保证给定的图是一棵树。

接下来一行包含 $m$ 个不同的整数 $1⩽x_i⩽n−1$，表示特定道路的索引（根据输入顺序）。

接下来的 $k$ 行，每行包含两个整数 $1⩽s_i,t_i⩽n$，表示旅游路线从 $s_i$ 到 $t_i$。

输出格式

输出你需要选择的最少旅游路线数量，以及达到这个最少数量的方案数，答案对 $998244353$ 取模。

如果无法经过所有特定的道路，输出 −1。

3 2 2
1 2
1 3
1 2
2 3
1 2

1 1

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

2 2

解释 #2

对于样例 2，我们需要选择至少 $2$ 条路线，有两种可能的方案：

1. 路线 $1$ 和路线 $2$，路线 $1$ 覆盖道路 $1$ 和道路 $3$，路线 $2$ 覆盖道路 $1$ 和道路 $5$。
2. 路线 $2$ 和路线 $3$，路线 $2$ 覆盖道路 $1$ 和道路 $5$，路线 $3$ 覆盖道路 $3$。