People of Wakanda really love biking. Each city has their own bike hub. You can pick a bike from any hub! After arrival at your destination city, you just need to return the bike to the bike hub.
On a typical morning, each bike hub has K bikes. Whole day people move randomly. So at the end of the day the number of bikes in the hubs gets changed. It can be greater than, less than or equal to K. We need to re-distribute the bikes so that it is the same as in the morning. So after shuffling each bike hub should have exactly K bikes again.
Wakanda country consists of N cities and there are N-1 bi-directional roads between the cities. Every city is reachable from every city by roads.
The Strawhat company is responsible for this bike management system. They have a giant truck of unlimited capacity to move bikes. Their policy is that they will visit all roads exactly twice, but can visit any city multiple times.
Now you need to find any possible route such that all the conditions are met. You can start from any city. From any bike hub you can collect any numbers of the bikes and similarly unload any numbers of bikes from the truck!
Input
The First line of the input contains a single integer T (1 ≤ T ≤ 25) denoting the number of test cases. The description of T test cases as follows:
- The first line of each test case contains two integers N (1 ≤ N ≤ 10000) and K (1 ≤ K ≤ 1000).
- Each of the next N−1 lines contains two space-separated integers x and y denoting that cities x and y are connected by a road.
- The last line contains N integers denoting the city i has xi (0 ≤ xi ≤ 107) bikes. It is guaranteed that sum of all xi will be N x K.
Output
For every test case, you must print the case number, followed by YES if there is a possible route, otherwise NO.
If there is a possible route, then print 2N-1 additional lines describing the order of the road traversal. Each line should have 2 integers: u and p.
Where, u indicates the city you will go to and p indicates how many bikes you collect from or give to the bike hub of this city. Non-negative p means you are putting p bikes to the bike hub and negative p means you are taking bikes from bike hub. First line indicates you start from this city.
Please check the samples for further clarification.
Sample
| Sample Input | Sample Output |
|---|---|
2 2 100 1 2 200 0 5 20 1 4 2 4 4 5 3 4 31 7 22 23 17 | Case 1: YES 2 0 1 -100 2 100 Case 2: YES 4 -13 2 13 4 -3 5 3 4 0 1 -11 4 11 3 -2 4 2 |
Notes
In the first case, we start from the bike hub of city 2 and do nothing. Then go to the bike hub of the city 1 and take 100 bikes from there. After this, return to city 2 and put 100 bikes on the bike hub.
Similarly in the second case, we start from the bike hub of the city 4 and take 13 bikes. Then move to city 2 and give 13 bikes and so on.