Problem Description

You are given a tree $G$ with $n$ nodes and an integer $E$.

You need to construct an integer edge weight $w_i$ for each edge of the tree $G$, such that:

• $1 \le w_i \le 10^9$;
• Choose a node $u$ uniformly at random. The expected value of $\max\limits_{v=1}^n\operatorname{dis}(u,v)$, taken modulo $998244353$, is equal to $E$;

or report that there is no solution.

Here, $\operatorname{dis}(u,v)$ denotes the sum of edge weights on the simple path between nodes $u$ and $v$.

If you do not know how to compute an expectation modulo $998244353$, please refer to P2613 Template: Modulo of Rational Numbers.

Input Format

The first line contains an integer $n$.

The next $n-1$ lines each contain two positive integers $u_i,v_i$, indicating that there is an edge $(u_i,v_i)$ between nodes $u_i$ and $v_i$ in the tree $G$.

The next line contains an integer $E$.

Output Format

Output one line or $n-1$ lines:

• If there is a solution, output $n-1$ lines, each containing an integer $w_i$, representing the edge weight of edge $(u_i,v_i)$ in your constructed tree $G$.
• If there is no solution, output one line containing an integer $-1$.

Any output that satisfies the requirements will be accepted.

3
1 2
2 3
665496238

1
2

Hint

"Sample Explanation #1"

All values of $\operatorname{dis}$ are shown in the table below, where the red numbers are the maximum $\operatorname{dis}$ values for the node at the beginning of each row.

You can verify that $E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353}$.

Constraints

For all testdata, $2\le n\le 10^5$, $1 \le u_i,v_i \le n$, $0\le E < 998244353$. It is guaranteed that the input forms a tree.

You can get the score for this problem only if you pass all test points.

Translated by ChatGPT 5