P4321 Random Walk

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

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

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