题目描述

小 L 正在玩游戏，游戏地图是一颗 $n$ 个节点的树，定义一条树上路径的长度为路径上所有边的边权之和，路径可以重复经过点和边。特别的，若路径不包含任何边，则其长度为 $0$。

小 L 会选择一个点作为必经点 $t$，接着，小 L 会设置每条边的边权，使得边的边权构成一个 $1$ 到 $n-1$ 的排列。

定义：小 L 的得分为 $\sum_{1 \leq u,v \leq n} \operatorname{dist}(u,v)$，其中 $\operatorname{dist}(u,v)$ 为在经过必经点 $t$ 的前提下，长度最小的从 $u$ 到 $v$ 的路径的长度。

小 L 希望最大化自己的得分，请你解答以下问题：

第一问：求他得分的最大值对 $998244353$ 取模的值。

第二问：求若要最大化他的得分，小 L 应该选择的必经点 $t$ 和小 L 每条边应设置的边权。

输入格式

一行一个整数 $n$，表示节点数。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示树上一条连接点 $u$ 和点 $v$ 的边。

输出格式

输出共三行。

第一行一个整数，表示【小 L 得分的最大值】对 $998244353$ 取模的值。

第二行一个整数，表示小 L 应该选择的必经点 $t$，如有多种 $t$ 符合题意，请输出最小的 $t$。

第三行 $n-1$ 个整数，按边的输入顺序依次给出小 L 每条边应设置的边权。如有多种答案，请输出边权的字典序最小的答案。

注意：在小 L 得分最大的前提下，请首先最小化 $t$，其次最小化边权的字典序。

这里“边权的字典序”是指按边的输入顺序将边的边权看作一个排列，这个排列的字典序。

5
1 2
1 3
2 4
2 5

280
3
3 4 1 2

7
5 1
1 7
6 2
2 1
4 5
3 2

1106
4
5 1 2 4 6 3

10
3 6
7 3
8 10
5 9
9 1
4 8
1 8
2 3
6 10

5240
5
4 1 6 9 8 2 7 3 5

10
1 2
1 3
3 4
3 5
2 6
6 7
7 8
8 9
9 10

5660
10
4 3 1 2 5 6 7 8 9

20
5 18
16 11
6 15
7 14
8 7
10 20
3 4
14 6
9 8
18 11
17 4
11 10
4 11
2 13
13 12
12 15
15 20
19 9
1 8

79480
19
1 2 14 16 17 12 3 15 18 7 4 11 9 5 8 10 13 19 6

10
7 8
3 2
6 7
2 10
8 3
4 1
9 2
1 3
5 7

4340
5
8 6 1 2 7 3 4 5 9 

见附件

见附件

提示

本题采用捆绑测试。

对于所有数据，$1\le n\le 10^5$。

特殊性质 1：存在一个对点重标号的方案，使得第 $i$ 条边为 $(1,i+1)$。

特殊性质 2：存在一个对点重标号的方案，使得第 $i$ 条边为 $(i,i+1)$。