#898 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	20	$N\leq2000$ ; $Q\leq2000$ .
2	25	对每个 $1\leq i<N$ ，顶点与之间都有一条边。

样例 1

样例输入

样例输出

3 3 5 5 3

三个询问的路径依次为 $2,1,3,4$ 、 $4,3,5$ 、 $1,2$ 。按顶点编号顺序，最终的值为。