暂无测试数据。

题目描述

蒜头君最近在学有机化学，刚刚学会了烷烃的命名。

所谓烷烃，可以姑且当作是一棵树。

对于下面给出的图，可以把 $\text{CH}_n,n=1,2,3,4。\text{（注意：如果 n 为1，此时1省略不写。）} $ 当成一个树的节点。

下面给出命名规则：

• 找主链：找出烷烃最长的一条链，如果有多条最长链，选支链最多的一条。

• 排编号：
  • 以离 左右端最近的支链 更近的一端开始编号。
  • 若两端一样近，则选最近支链 节点数 较小的一端。(若有多个最近支链，用 节点数 最小的那个支链来判断)

(保证不存在左右最近支链的 距离 和 最小节点数 均相等的情况)

• 写名称：对于每个支链有两个属性：大小 、对应主链的编号
  • 以 大小 为第一关键字，对应主链的编号 为第二关键字从小到大排序。
  • 你只需要输出每个支链 【排好序后的序号 $\times$ 大小 $\times$ 对应主链的编号】的和，以及主链的长度即可。
• 按照上述命名规则，答案唯一。

输出格式

数据范围

输入描述

第一行给出 $n$ 表示烷烃的大小

接下来 $n-1$ 行每行给出 $u,v$ 表示 $u,v$ 有一条边。

输出描述

第一行输出每个支链 【排好序后的序号 $\times$ 大小 $\times$ 对应主链的编号】的和，答案对 $998244353$ 取模。

第二行输出主链的长度即可。

数据范围

数据占比	性质
$20\%$	$n\leq 20$
$30\%$	$n\leq 100000$，保证最长链只有一条
$50\%$	$n\leq 100000$

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

19
6