题目描述
给定一棵包含 $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$ 之间简单路径上的边权和。
输入格式
第一行输入一个整数 $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$。
所有满足要求的输出均可通过。
样例 1 输入
3 1 2 2 3 665496238
样例 1 输出
1 2
样例 1 解释
所有 $\operatorname{dis}$ 的值如下表，其中标红的是行首结点的 $\operatorname{dis}$ 的最大值。
| $\operatorname{dis}$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $0$ | $1$ | $\color{red}3$ |
| $2$ | $1$ | $0$ | $\color{red}2$ |
| $3$ | $\color{red}3$ | $2$ | $0$ |
可以验证，$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$，保证输入数据形成一棵树。