Description

Given a tree with $n$ nodes, you start from node $x$. Each time, you randomly choose an edge adjacent to the current node with equal probability and walk along it.

There are $Q$ queries. In each query, you are given a set $S$. Starting from $x$, you keep doing the random walk until every node in $S$ has been visited at least once. Find the expected number of steps.

In particular, node $x$ (the starting node) is considered to have been visited once at the beginning.

Output the answer modulo $998244353$.

Input Format

The first line contains three positive integers $n, Q, x$.

The next $n - 1$ lines each contain two positive integers $(u, v)$ describing an edge of the tree.

The next $Q$ lines describe the queries. Each line starts with an integer $k$ denoting the size of the set, followed by $k$ pairwise distinct integers denoting the set $S$.

Output Format

Output $Q$ lines. Each line contains a non-negative integer representing the answer.

3 5 1
1 2
2 3
1 1
1 3
2 2 3
3 1 2 3
2 1 2

0
4
4
4
1

Hint

For $20\%$ of the testdata, $1 \leq n, Q \leq 5$.

For another $10\%$ of the testdata, the given tree is a chain.

For another $10\%$ of the testdata, for all queries $k = 1$.

For another $30\%$ of the testdata, $1 \leq n \leq 10$ and $Q = 1$.

For $100\%$ of the testdata, $1 \leq n \leq 18$, $1 \leq Q \leq 5000$, and $1 \leq k \leq n$.

Translated by ChatGPT 5