CF1141G.Privatization of Roads in Treeland

Treeland consists of $n$ cities and $n-1$ roads. Each road is bidirectional and connects two distinct cities. From any city you can get to any other city by roads. Yes, you are right — the country's topology is an undirected tree.

There are some private road companies in Treeland. The government decided to sell roads to the companies. Each road will belong to one company and a company can own multiple roads.

The government is afraid to look unfair. They think that people in a city can consider them unfair if there is one company which owns two or more roads entering the city. The government wants to make such privatization that the number of such cities doesn't exceed $k$ and the number of companies taking part in the privatization is minimal.

Choose the number of companies $r$ such that it is possible to assign each road to one company in such a way that the number of cities that have two or more roads of one company is at most $k$. In other words, if for a city all the roads belong to the different companies then the city is good. Your task is to find the minimal $r$ that there is such assignment to companies from $1$ to $r$ that the number of cities which are not good doesn't exceed $k$.

The picture illustrates the first example ($n=6, k=2$). The answer contains $r=2$ companies. Numbers on the edges denote edge indices. Edge colors mean companies: red corresponds to the first company, blue corresponds to the second company. The gray vertex (number $3$) is not good. The number of such vertices (just one) doesn't exceed $k=2$. It is impossible to have at most $k=2$ not good cities in case of one company.

Treeland 由 $n$ 座城市和 $n-1$ 条道路组成。每条道路都是双向的，连接两个不同的城市。从任意一座城市出发，均可经由道路到达其他任意一座城市。没错，您猜对了——该国的拓扑结构是一棵无向树。

Treeland 中存在若干家私营道路公司。政府决定将道路出售给这些公司。每条道路将归属一家公司，且一家公司可拥有多条道路。

政府担心其决策显得不公平。他们认为，若某座城市中存在一家公司拥有两条或更多条通往该城市的道路，则该城市的居民可能认为政府不公平。因此，政府希望进行一种私有化方案，使得此类城市的数量不超过 $k$，同时参与私有化的公司数量尽可能少。

请确定公司数量 $r$，使得可以将每条道路分配给编号为 $1$ 至 $r$ 的某一家公司，且满足：具有两条或更多条属于同一家公司道路的城市数量至多为 $k$。换言之，若某座城市的所有相连道路均属于不同公司，则称该城市为“良好城市”。您的任务是找出最小的 $r$，使得存在一种将道路分配给编号为 $1$ 至 $r$ 的公司的方案，使得“非良好城市”的数量不超过 $k$。

该图展示了第一个样例（$n=6, k=2$）。答案中 $r=2$，即使用两家公司。边上的数字表示边的编号；边的颜色代表所属公司：红色对应第一家公司，蓝色对应第二家公司。灰色顶点（编号为 $3$）不是良好城市。此类顶点的数量（仅一个）未超过 $k=2$。若仅使用一家公司，则无法使非良好城市的数量不超过 $k=2$。

The first line contains two integers $n$ and $k$ ($2 \le n \le 200000, 0 \le k \le n - 1$) — the number of cities and the maximal number of cities which can have two or more roads belonging to one company.

The following $n-1$ lines contain roads, one road per line. Each line contains a pair of integers $x_i$, $y_i$ ($1 \le x_i, y_i \le n$), where $x_i$, $y_i$ are cities connected with the $i$-th road.

第一行包含两个整数 $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$），表示第 $i$ 条道路连接的城市 $x_i$ 和 $y_i$。

In the first line print the required $r$ ($1 \le r \le n - 1$). In the second line print $n-1$ numbers $c_1, c_2, \dots, c_{n-1}$ ($1 \le c_i \le r$), where $c_i$ is the company to own the $i$-th road. If there are multiple answers, print any of them.

第一行输出所需的 $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$ 条道路所属的公司。若存在多个答案，输出任意一个即可。