给你一棵由 $$$n$$$ 顶点组成的树,编号从 $$$1$$$ 到 $$$n$$$。树是无环的连通无向图。
对于每个 $$$i=1,2, \ldots, n$$$,令 $$$w_i$$$ 为第 $$$i$$$ 个顶点的权重。如果一个顶点的权重等于其所有邻居权重的总和,则该顶点被称为好顶点。
最初,所有节点的权重均未分配。为树的每个顶点分配正整数权重,使得树中好顶点的数量最大化。如果有多种方法可以做到这一点,则必须找到一种使树中所有顶点的权重之和最小化的方法。
输入
第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。
然后是 $$$n−1$$$ 行。它们每个都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$) 表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证边形成一棵树。
输出
在第一行中打印两个整数 - 良好顶点的最大数量以及该最大值的最小可能权重总和。
在第二行中打印 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$1\le w_i\le 10^9$$$) — 分配给每个顶点的相应权重。可以证明存在满足这些约束条件的最优解。
如果有多个最优解,您可以打印任意一个。
示例
输入 #1
4 1 2 2 3 2 4
输出 #1
3 4 1 1 1 1
输入 #2
3 1 2 1 3
输出 #2
2 3 1 1 1
输入 #3
2 1 2
输出 #3
2 2 1 1
输入#4
9 3 4 7 6 2 1 8 3 5 6 1 8 8 6 9 6
输出#4
6 11 1 1 1 1 1 1 1 3 1
注意
这是第一个测试用例的树:
这是第二个测试用例的树: