Maximizing Score on a Weighted Tree Game

In this problem, you are given a tree with n nodes. The tree’s edges have weights that form a permutation of the integers from 1 to n-1. You are also allowed to choose a special vertex t (called the mandatory vertex).

For any two vertices u and v, define a t-path as a path from u to v that must include t. (Note that the path may pass through vertices and edges more than once; in particular, if no edge is used the length is defined to be 0.) The length of a path is the sum of the weights on the edges used. In a tree, if we require that the path goes through t then the minimum‐length path is unique and is given by the concatenation of the unique simple path from u to t and from t to v (with a possible double count of t, which is irrelevant since only edge weights count).

The score is defined as

$$\text{Score} = \sum_{u=1}^{n}\sum_{v=1}^{n} \operatorname{dist}(u,v), $$

where, given the mandatory vertex t,

$$\operatorname{dist}(u,v)=d(u,t)+d(t,v),$$

and d(u,t) is the distance from u to t computed along the tree with the assigned weights. Equivalently, if you root the tree at t, then for every edge from a parent to a child with subtree size s, its weight contributes to the distances from t to all vertices in that subtree and thus its total contribution is s multiplied by its assigned weight.

Small L wants to maximize his score by choosing the mandatory vertex t and assigning the edge weights appropriately. That is, for the tree rooted at t, if for every edge (from parent to child) the subtree size is computed as the number of vertices in the subtree of the child, then if the contributions are collected into a list \(S = \{s_e\}\) of length n-1, you are allowed to assign weights (which form a permutation of \(\{1,2,\ldots,n-1\}\)) to maximize $$\sum_{e}\; s_e \times w(e).$$

The optimal strategy is to sort the contributions in descending order and pair the largest contribution with the largest weight, the second largest contribution with the second largest weight, and so on. The final score is then given in terms of these weighted sums by

$$\text{Score} = 2n \times \Biggl(\sum_{i=1}^{n-1} s_{(i)} \times (n - i)\Biggr) \pmod{998244353}, $$

where \(s_{(1)} \ge s_{(2)} \ge \cdots \ge s_{(n-1)}\) is the sorted list of contributions computed when the tree is rooted at t.

Your task is to:

1. Compute the maximum possible score modulo \(998244353\).
2. Output a corresponding choice of mandatory vertex t (an integer between 1 and n) and an assignment of weights to the n-1 edges (in the original input order) that attains this maximum score.

If n = 1, then the score is 0 and no edge weights are assigned. It is guaranteed that the input forms a tree.

Note: All formulas are written in LaTeX format.

inputFormat

The first line contains an integer n (\(1 \le n \le 2000\)), the number of nodes in the tree. The following n-1 lines each contain two integers u and v (\(1 \le u,v \le n\)), indicating that there is an edge between vertices u and v.

outputFormat

On the first line, output the maximum possible score modulo \(998244353\). On the second line, output the chosen mandatory vertex t. Then, output n-1 lines: the i-th of these lines corresponds to the i-th edge in the input, and contains the weight assigned to that edge.

sample

1

0
1