Star Tree

頂点に $1$ から $N$ までの番号が付いた木が与えられる。最初、すべての頂点の値は $0$ である。

次の形式のクエリを $Q$ 個処理する。

• $x\ y$: 頂点 $x$ から頂点 $y$ への唯一の単純パス上の頂点を順に $a_1,a_2,\ldots,a_k$ とする。各 について、頂点 の値に を加える。ここで 、、 である。

パスの両端の頂点も含む。クエリの向きを逆にすると加算する値が変わる場合がある。すべてのクエリを処理した後、各頂点の値を $998\,244\,353$ で割った余りを求めよ。

入力は次の形式で与えられる。最初の行に頂点数 $N$ とクエリ数 $Q$ が与えられる。続く $N-1$ 行の $u_i,v_i$ は木の辺を表し、その後の 行の はクエリを表す。 のとき辺の行はなく、 のときクエリの行はない。

頂点 $1,2,\ldots,N$ の最終的な値をそれぞれ $998\,244\,353$ で割った余りを、空白区切りで一行に出力せよ。

• $1\leq N\leq500\,000$.
• $0\leq Q\leq500\,000$.
• $1\le u_i$, ().