5815：Golden Week

The ACM kingdom has N cities, numbered from 1 to N. The capital is numbered 1. There are N – 1 roads each connecting two cities in the kingdom such that there exactly one path between any pair of cities.

Now the Golden Week Vocation is coming. M travelers living in the capital are going to travel to other cities. Every traveler will start from the capital, and the ith traveler has chosen city Ci as his destination. As a manager of the travel agencies, Mr. Chopsticks decides to assign prices to the roads in the kingdom during the vocation. After some investigation, Mr. Chopsticks has found that every traveler has a budget for his trip, and if the total price of the roads in the path from the capital to his destination city is larger than his budget, he will give up his trip; otherwise he will pay for it to the travel agencies. Mr. Chopsticks wants to assign prices to roads so as to maximize the agencies’ revenue. Could you help him? Each road should be assigned a price between 0 and 1000,000,000 inclusive.

The input begins with an integer T (T<=50), indicating the number of test cases. Each case begins with two integers N and M (2 <= N <= 1000, 1 <= M <= 1000), indicating the number of cities and the number of travelers respectively. Then N – 1 lines follow, where the ith line contains two integers $u_i$ and $v_i$ $(1 \leq u_i, v_i \leq N)$ indicating that the ith road connects the cities $u_i$ and $v_i$. The next M lines each contain two integers $C_i$ and $B_i$ $(1 \leq C_i \leq N, 1 \leq B_i \leq 1000 000 000)$, indicating the ith traveler’s destination and budget respectively.

For each case, output a line containing the maximum revenue, followed by a line containing N – 1 nonnegative integers, separated by one space, in which the ith integer denotes the price of the ith road. If there are multiple optimum solutions, output any of them.