题目描述

给定一棵有 $n$ 个节点的无根树，节点编号为 $1, 2, \dots, n$。定义树上两点 $i$ 和 $j$ 之间的距离 $\text{dis}(i, j)$ 为两点间简单路径上的边数。

存在 $k$ 个关键点 $a_1, a_2, \dots, a_k$，对于每个节点 $v$，$f(v)$ 表示满足 $\text{dis}(v, a_i)$ 最小的索引 $i$；若存在多个索引 $i$ 满足距离最小，则选择其中最小的 $i$。

现在给出 $f(1), f(2), \dots, f(n)$，要求计算满足该 $f$ 数组的关键点组合 $(a_1, a_2, \dots, a_k)$ 的组数。答案需对 $998244353$ 取模，若不存在合法组合则输出 $0$。

输入格式

• 第一行：整数 $T$，表示测试数据组数。
• 对于每组测试数据：
  1. 第一行：两个整数 $n$ 和 $k$（空格分隔），分别表示节点个数和关键点个数。
  2. 接下来 $n-1$ 行：每行两个整数 $u$ 和 $v$（空格分隔），表示树中的一条边。
  3. 最后一行：$n$ 个整数 $f(1), f(2), \dots, f(n)$（空格分隔），数据不保证存在合法关键点组合。

输出格式

对于每组测试数据，输出一个整数，表示合法关键点组合的组数（对 $998244353$ 取模）。

样例 1

输入

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

输出

0
1
2

说明

• 第二组数据：唯一合法的关键点组合为 $(1, 2)$。
• 第三组数据：合法组合有两个，分别为 $(2, 1)$ 和 $(3, 1)$。
• 注意：距离相同时，选择的是最小的索引 $i$，而非最小的 $a_i$。

样例 2

输入

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

输出

13

数据范围与提示

• 所有数据：$1 \leq T \leq 10$，$2 \leq k \leq n \leq 3 \times 10^3$，$1 \leq f(i) \leq k$。
• 测试点信息如下：

其中，特殊性质 A 为“树是一条链”，特殊性质 B 为“$k=2$”。