Description

Country H has $N$ cities.

In the next $M$ days, Xiao c will go to look for Xiao w, but Xiao c does not know the exact location of Xiao w, so Xiao c decides to randomly choose one road to walk each time until meeting Xiao w.

Xiao c knows that Xiao w can only be in one of the $n$ cities $c_1, c_2.. c_n$. Xiao c wants to know, in the worst case, the expected number of roads Xiao c needs to traverse before meeting Xiao w.

All edges in country H are undirected. Between any two cities, there is at most one road directly connecting them, and no road connects the same city to itself.

At any time, in country H there do not exist cities $u$ and $v$ such that $v$ cannot be reached from $u$.

Input Format

The first line contains two positive integers $N, E$, representing the number of cities and the number of edges in country H.

Lines 2 to $E+1$ each contain two positive integers $u, v$, indicating there is a road between city $u$ and city $v$.

Line $E+2$ contains one positive integer $M$.

Lines $E+3$ to $E+M+2$ each contain $n+2$ positive integers: the first integer is $n$, followed by $n$ distinct integers $c_i$, and the last integer $s$ indicates the city where Xiao c is located.

Output Format

Output $M$ lines, each containing a single integer $r$ representing the answer.

If the expected value you compute is $\frac{q}{p}$, where $p, q$ are coprime, then you should output an $r$ such that $r\times p \equiv q(\mathrm{mod}\ 998244353)$ and $0\leq r < 998244353$. It can be proved that such an $r$ is unique.

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

1
4
4

Hint

The roads of country H form a chain, so in the worst case Xiao w is at the deepest node (taking Xiao c’s city as the root).

For the first day, Xiao c is in city 1, the deepest node is 2, city 1 can only reach city 2, and the expected number of roads to reach it is 1.

For the second day, Xiao c is in city 1, the deepest node is 3, and the computed expectation is 4 roads to reach it.

The third day is the same as the second day.

The worst case means going through all $n$ possible cities at least once.

Subtask 1: 10 points, $N = 4, M = 12$.

Subtask 2: 15 points, $N =10, M = 100000$.

Subtask 3: 15 points, $N = 18, M = 1$.

Subtask 4: 10 points, $N = 18, M = 99995$, the graph is a chain.

Subtask 5: 10 points, $N = 18, M = 99996$, all $s$ are the same.

Subtask 6: 15 points, $N = 18, M = 99997$, $E = N-1$.

Subtask 7: 15 points, $N = 18, M = 99998$, all $s$ are the same.

Subtask 8: 10 points, $N = 18, M = 99999$.

Constraints for all testdata: $1\leq N\leq 18, 1\leq M\leq 100000, 1\leq E\leq \frac{N(N-1)}{2}$.

Translated by ChatGPT 5