某场比赛

题目描述

有 $N$ 名玩家，分别是玩家 $1$、玩家 $2$、……、玩家 $N$，参加一个比赛锦标赛。就在锦标赛开始前，每名玩家各自组成一支队伍，因此总共有 $N$ 支队伍。

锦标赛共有 $N-1$ 场比赛。每场比赛选出两支不同的队伍。一支队伍先手，另一支队伍后手。每场比赛恰好有一支队伍获胜。具体地，对于每个 $i = 1, 2, \ldots, N-1$，第 $i$ 场比赛按以下方式进行。

• 包含玩家 $p_i$ 的队伍先手，包含玩家 $q_i$ 的队伍后手。
• 设先手和后手队伍的人数分别为 $a$ 和 $b$。先手队伍以概率 $\frac{a}{a+b}$ 获胜，后手队伍以概率 $\frac{b}{a+b}$ 获胜。
• 然后，两支队伍合并为一支队伍。

每场比赛的结果与其他比赛相互独立。

对于 $N$ 名玩家中的每一个，输出该玩家所在的队伍在整个锦标赛中获胜次数的期望值，对 $998244353$ 取模。

如何对 $998244353$ 取模输出期望值

可以证明所求期望值总是有理数。此外，本题的数据范围保证，若所求期望值表示为既约分数 $\frac{y}{x}$，则 $x$ 不被 $998244353$ 整除。

此时，存在唯一一个 $0$ 到 $998244352$（含）之间的整数 $z$，满足 $xz \equiv y \pmod{998244353}$。输出这个 $z$。

输入格式

输入按以下格式从标准输入给出：

$N$
$p_1$ $q_1$
$p_2$ $q_2$
$\vdots$
$p_{N-1}$ $q_{N-1}$

输出格式

按以下格式，用空格分隔输出 $E_i$（玩家 $i$ 所在的队伍在整个锦标赛中获胜次数的期望值，对 $998244353$ 取模）：

$E_1$ $E_2$ $\ldots$ $E_N$

样例

5
1 2
4 3
5 3
1 4

698771048 698771048 964969543 964969543 133099248

将由玩家 $x_1$、玩家 $x_2$、$\ldots$、玩家 $x_k$ 组成的队伍记作队伍 $\lbrace x_1, x_2, \ldots, x_k \rbrace$。

第一场比赛由队伍 $\lbrace 1 \rbrace$（包含玩家 $1$）和队伍 $\lbrace 2 \rbrace$（包含玩家 $2$）进行。队伍 $\lbrace 1 \rbrace$ 以概率 $\frac{1}{2}$ 获胜，队伍 $\lbrace 2 \rbrace$ 以概率 $\frac{1}{2}$ 获胜。然后，两支队伍合并为队伍 $\lbrace 1, 2 \rbrace$。

第二场比赛由队伍 $\lbrace 4 \rbrace$（包含玩家 $4$）和队伍 $\lbrace 3 \rbrace$（包含玩家 $3$）进行。队伍 $\lbrace 4 \rbrace$ 以概率 $\frac{1}{2}$ 获胜，队伍 $\lbrace 3 \rbrace$ 以概率 $\frac{1}{2}$ 获胜。然后，两支队伍合并为队伍 $\lbrace 3, 4 \rbrace$。

第三场比赛由队伍 $\lbrace 5 \rbrace$（包含玩家 $5$）和队伍 $\lbrace 3, 4 \rbrace$（包含玩家 $3$）进行。队伍 $\lbrace 5 \rbrace$ 以概率 $\frac{1}{3}$ 获胜，队伍 $\lbrace 3, 4 \rbrace$ 以概率 $\frac{2}{3}$ 获胜。然后，两支队伍合并为队伍 $\lbrace 3, 4, 5 \rbrace$。

第四场比赛由队伍 $\lbrace 1, 2 \rbrace$（包含玩家 $1$）和队伍 $\lbrace 3, 4, 5 \rbrace$（包含玩家 $4$）进行。队伍 $\lbrace 1, 2 \rbrace$ 以概率 $\frac{2}{5}$ 获胜，队伍 $\lbrace 3, 4, 5 \rbrace$ 以概率 $\frac{3}{5}$ 获胜。然后，两支队伍合并为队伍 $\lbrace 1, 2, 3, 4, 5 \rbrace$。

包含玩家 $1, 2, 3, 4, 5$ 的队伍在整个锦标赛中获胜次数的期望值 $E_1, E_2, E_3, E_4, E_5$ 分别为 $\frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}$。

15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le p_i, q_i \le N$
• 在第 $i$ 场比赛开始前，玩家 $p_i$ 和玩家 $q_i$ 属于不同的队伍。
• 输入均为整数。