Treeland 由 $$$n$$$ 城市和 $$$n-1$$$ 道路组成。每条道路都是双向的,连接两个不同的城市。从任何城市,您都可以通过公路到达任何其他城市。是的,你是对的——国家的拓扑结构是一棵无向树。
Treeland 有一些私人公路公司。政府决定将道路出售给这些公司。每条道路都属于一家公司,一家公司可以拥有多条道路。
政府害怕看起来不公平。他们认为,如果一个公司拥有两条或更多条进入城市的道路,城市里的人们就会认为他们不公平。政府希望进行这样的私有化,即此类城市的数量不超过$$$k$$$,并且参与私有化的公司数量最少。
选择公司数量$$$r$$$,以便可以将每条道路分配给一家公司,这样拥有一家公司的两条或更多道路的城市数量最多为$$$k$$$。换句话说,如果一个城市的所有道路都属于不同的公司,那么这个城市就很好。您的任务是找到最小的 $$$r$$$,从 $$$1$$$ 到 $$$r$$$ 的公司有这样的分配,使得不好的城市数量不超过 $$$k$$$。
该图展示了第一个示例($$$n=6,k=2$$$)。答案包含 $$$r=2$$$ 公司。边缘上的数字表示边缘索引。边缘颜色代表公司:红色对应第一家公司,蓝色对应第二家公司。灰色顶点(数字$$$3$$$)不好。这样的顶点数量(只有一个)不超过$$$k=2$$$。一家公司不可能最多有$$$k=2$$$个不好的城市。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 200000, 0 \le k \le n - 1$$$) — 城市数量以及可以拥有属于一家公司的两条或更多道路的城市的最大数量。
以下 $$$n-1$$$ 行包含道路,每行一条道路。每行包含一对整数 $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$),其中 $$$x_i$$$, $$$y_i$$$ 是与第 $$$i$$$ 条道路相连的城市。
输出
在第一行中打印所需的 $$$r$$$ ($$$1 \le r \le n - 1$$$)。在第二行中打印 $$$n-1$$$ 数字 $$$c_1, c_2, \dots, c_{n-1}$$$ ($$$1 \le c_i \le r$$$),其中 $$$c_i$$$ 是拥有第 $$$i$$$ 条道路的公司。如果有多个答案,请打印其中任何一个。
示例
输入 #1
6 2 1 4 4 3 3 5 3 6 5 2
输出 #1
2 1 2 1 1 2
输入 #2
4 2 3 1 1 4 1 2
输出 #2
1 1 1 1
输入 #3
10 2 10 3 1 2 1 3 1 4 2 5 2 6 2 7 3 8 3 9
输出 #3
3 1 1 2 3 2 3 1 3 1