There are n cities in the Rainbow Island, connected by n1 bidirectional roads.Lizishu is fond of travel. In the ithof each m years, she would go for travel from city xi with ki Yuanand she would cost 1 Yuan leaving a city to an adjacent one. For seeing more scenery, she wants to go to as manydifferent cities as possible.Now you are given the map of the Rainbow Island and you should tell Lizishu the maximum number of different cities she can reach every year.Note that every time she can only go to an adjacent city and cost 1 Yuan.
There are n cities in the Rainbow Island, connected by n−1 bidirectional roads. Lizishu is fond of travel. In the ith of each m years, she would go for travel from city xi with ki Yuan and she would cost 1 Yuan leaving a city to an adjacent one. For seeing more scenery, she wants to go to as many different cities as possible. Now you are given the map of the Rainbow Island and you should tell Lizishu the maximum number of different cities (including xi) she can reach every year. Note that every time she can only go to an adjacent city and cost 1 Yuan.
（图片来源网络，侵删）
