题目描述

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$是唯一的

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$ 个可能的城市至少一遍

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}$