1236 : 生成树计数

Description

给定一个有 \(n\) 个节点的树，初始节点编号为从 \(1\) 到 \(n\)，再给定一个长度为 \(n-1\) 节点序列，我们将按照序列的顺序对树进行操作。

对于每个操作，如果当前要操作的节点是 \(x\)，首先创建一个新节点，编号为 \(x+n\)。对于任意整数 \(i\in [1,n]\)，如果边 \((x,i)\) 存在：

• 如果节点 \(i+n\) 不存在，我们连接 \((x+n,i)\)。

• 如果节点 \(i+n\) 存在（在这种情况下，边 \((x,i+n)\) 总是存在的），我们连接 \((x+n,i+n)\) 并删除边 \((x,i+n)\)。

对于每个操作后得到的新图，请计算其生成树的数量，并对 \(998244353\) 取模。

Input

第一行包含一个整数 \(n \; (1 \le n \le 5000)\)，表示树的大小。

接下来的 \(n-1\) 行，每行包含两个数字 \(u\) 和 \(v\;(1\le u,v\le n)\)，表示树中的边 \((u,v)\)。保证输入形成一棵合法的树。

最后一行包含 \(n-1\) 个不同的数字 \(b_i\;(1 \le b_i \le n)\)，表示按顺序进行操作的节点序列。

Output

输出 \(n-1\) 行，第 \(i\) 行输出一个整数表示执行完第 \(i\) 个操作后图中生成树的数量，答案对 \(998244353\) 取模。

Sample

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

4
4
6
1

Hint

Source

Author

SYSU