题目描述

H 国有 $N$ 个城市。

在接下来的 $M$ 天，小 c 都会去找小 w，但是小 c 不知道小 w 的具体位置，所以小 c 决定每次随机找一条路走，直到遇到了小 w 为止。

小 c 知道小 w 只有可能是在 $c_1, c_2\dots c_n$ 这 $n$ 个城市中的一个，小 c 想知道在最坏情况下，小 c 遇到小 w 期望要经过多少条道路。

H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市。

任何时候，H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$。

输入格式

输入第 $1$ 行一个正整数 $N, E$，分别表示 H 国的城市数与边的数量。

输入第 $2$ 行至第 $E+1$ 行，每行两个正整数 $u, v$，分别表示城市 $u$ 到城市 $v$ 有一条道路。

输入第 $E+2$ 行一个正整数 $M$。

输入第 $E+3$ 行至第 $E+M+2$ 行每行 $n+2$ 个正整数，第一个正整数为 $n$，接下来 $n$ 个互不相同的正整数 $c_i$，最后一个正整数 $s$ 表示小 c 所在的城市。

输出格式

输出共 $M$ 行，每行一个正整数 $r$ 表示答案。

如果你计算出来的期望为 $\frac{q}{p}$，其中 $p, q$ 互质，那么你输出的 $r$ 满足 $r\times p \equiv q\pmod{998244353}$，且 $0\leq r < 998244353$，可以证明这样的 $r$ 是唯一的。

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

1
4
4

提示

【样例解释】

$H$ 国的道路构成一条链，所以最坏情况下就是小 w 在深度最大的点上（以小 c 所在的城市为根）。

对于第一天，小 c 所在的城市为 $1$，深度最大的点为 $2$，城市 $1$ 只能到达城市 $2$，期望经过 $1$ 条道路到达。

对于第二天，小 c 所在的城市为 $1$，深度最大的点为 $3$，计算的期望经过 $4$ 条道路到达。

第三天同第二天。

最坏情况也就是说经过所有 $n$ 个可能的城市至少一遍。

【数据范围】

• 子任务 $1$：$10$ 分，$N = 4, M = 12$。
• 子任务 $2$：$15$ 分，$N =10, M = 10^5$。
• 子任务 $3$：$15$ 分，$N = 18, M = 1$。
• 子任务 $4$：$10$ 分，$N = 18, M = 99995$，图是一条链。
• 子任务 $5$：$10$ 分，$N = 18, M = 99996$，所有的 $s$ 都相同。
• 子任务 $6$：$15$ 分，$N = 18, M = 99997$，$E = N-1$。
• 子任务 $7$：$15$ 分，$N = 18, M = 99998$，所有的 $s$ 都相同。
• 子任务 $8$：$10$ 分，$N = 18, M = 99999$。

对于所有数据，$1\leq N\leq 18, 1\leq M\leq 100000, 1\leq E\leq \frac{N(N-1)}{2}$。