题目描述

给定一棵包含 $n$ 个结点的树 $G$ 和一个整数 $E$。

你需要构造树 $G$ 中每条边的整数边权 $w_i$，满足：

• $1 \le w_i \le 10^9$；
• 均匀随机选择一个结点 $u$，$\max\limits_{v=1}^n\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$；

或报告无解。

其中，$\operatorname{dis}(u,v)$ 表示结点 $u,v$ 之间简单路径上的边权和。

如果你不知道如何计算期望对 $998244353$ 取模的结果，请移步 P2613 【模板】有理数取余。

输入格式

第一行输入一个整数 $n$。

接下来 $n-1$ 行，每行输入两个正整数 $u_i,v_i$，表示树 $G$ 中结点 $u_i,v_i$ 之间存在一条边 $(u_i,v_i)$。

接下来一行，输入一个整数 $E$。

输出格式

输出一行或 $n-1$ 行：

• 若有解，则输出 $n-1$ 行，每行输出一个整数 $w_i$，表示你构造的树 $G$ 中边 $(u_i,v_i)$ 的边权；
• 若无解，则输出一行，包含一个整数 $-1$。

所有满足要求的输出均可通过。

3
1 2
2 3
665496238

1
2

提示

「样例解释 #1」

所有 $\operatorname{dis}$ 的值如下表，其中标红的是行首结点的 $\operatorname{dis}$ 的最大值。

可以验证，$E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353}$。

「数据范围」

对于所有数据，$2\le n\le 10^5$，$1 \le u_i,v_i \le n$，$0\le E < 998244353$，保证输入数据形成一棵树。

只有你通过本题的所有测试点，你才能获得本题的分数。