随机漫游

题目描述

H 国有 $N$ 个城市 在接下来的 $M$ 天,小 c 都会去找小 w,但是小 c 不知道小 w 的具体位置,所以小 c 决定每次随机找一条路走,直到遇到了小 w 为止 小 c 知道小 w 只有可能是在 $c_1, c_2.. 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(\mathrm{mod}\ 998244353)$, 且$0\leq r < 998244353$,可以证明这样的 $r$是唯一的

输入输出样例

输入样例 #1

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

输出样例 #1

1
4
4

说明

$H$ 国的道路构成一条链,所以最坏情况下就是小 w 在深度最大的点上(以小 c 所在的城市为根) 对于第一天,小 c 所在的城市为 1,深度最大的点为 2,城市 1 只能到达城市 2,期望经过 1 条道路到达 对于第二天,小 c 所在的城市为 1,深度最大的点为 3,计算的期望经过 4 条道路到达 第三天同第二天 最坏情况也就是说经过所有 $n$ 个可能的城市至少一遍 subtask1 : 10分,$N = 4, M = 12$ subtask2 : 15分,$N =10, M = 100000$ subtask3 : 15分,$N = 18, M = 1$ subtask4 : 10分,$N = 18, M = 99995$,图是一条链 subtask5 : 10分,$N = 18, M = 99996$,所有的 $s$ 都相同 subtask6 : 15分,$N = 18, M = 99997$,$E = N-1$ subtask7 : 15分,$N = 18, M = 99998$,所有的 $s$ 都相同 subtask8 : 10分,$N = 18, M = 99999$ 对于所有数据 : $1\leq N\leq 18, 1\leq M\leq 100000, 1\leq E\leq \frac{N(N-1)}{2}$