东东是一名替身使者，但他那个名叫“铁树开花”的替身能力有点无聊——简单来说，“铁树开花”可以使一棵花的种子立刻发芽长大并开花。

现在有一个n个点C条边的无向图，图中结点编号为，且每条边边权均为1。在这个图上分布有m颗花的种子，编号为，每颗种子可以被两个参数（其中）描述，表示编号为i的种子埋在了编号为的结点内，且当其开花时，所有到结点的最短路长度不超过的结点都会被这朵花覆盖。

东东可以任意指定一个m的排列，然后依次对编号为的种子使用“铁树开花”能力，于是无向图中的每一个结点最终都可能被第中的某一朵花覆盖。需要注意的是，某个结点最终被哪朵花覆盖，取决于最后覆盖它的是哪朵花。比如在执行整一个开花顺序的过程中，结点u先后被编号为4, 8, 2的花覆盖，那么我们称结点u最终是被编号为2的花覆盖的。我们记最终被编号为i的花覆盖的结点的个数为。

东东很无聊，他想找到这样的一个排列，使得按照这个排列使用“铁树开花”能力后，能达成下面这个目标：

也就是说，要找到一个排列P，使得在考虑每一个可能的排列下最小的那个时，排列P对应的那个是最大的。显然这样的排列P可能有很多个，所以东东想要找出在所有满足上述条件的排列P中，字典序最小的那个。

东东自然是一眼看穿了答案，于是把这个问题扔给你来做。他为了不让你难过，保证了给出的无向图一定是一棵树。他希望你求出的值，以及在能达成这一目标且字典序最小的那个排列下，每朵花的值。