题目描述

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

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

请计算你需要选择的最少旅游路线数量，以及达到这一最小值可能的方法数，结果对 $998244353$ 取模。一个方案定义为选择的旅游路线集合。当且仅当存在一条旅游路线在一个方案中被选择而在另一个中未被选择时，两个方案被视为不同。

如果无法经过所有特定道路，则输出 $-1$。

题目保证答案对 $998244353$ 取模后非零。

输入格式

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

接下来的 $n−1$ 行，每行包含两个整数 $u$,$v$ ($1 \le u,v \le n$)，保证给定的图是一棵树。

接下来一行包含 $m$ 个不同的整数 $x_i(1 \le x_i \le n - 1)$，表示特定道路的编号（按输入顺序）。

接下来的 $k$ 行，每行包含两个整数 $s$,$t$ ($1 \le s,t \le n$) 表示旅游路线从 $s$ 到 $t$。

输出格式

输出你需要选择的最少旅游路线数量，以及达到这一最小值的方法数（对 $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$ 条路线，共有两种可能的方案：

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