It's wartime in the GOT world and T kingdoms are at battle. Each kingdoms consists of n cities connected by roads. Each road connects exactly two cities, and no two roads connect the same two cities. Furthermore, there is exactly one sequence of roads that connects any two cities.Each city provides pi power to its kingdom.

Each kingdom faces threats from other kingdoms. A Kingdom can choose a group of cities such that they are all connected by paths connecting only cities belonging to this group and accumulate their powers to face a threat.In order to face a threat, a kingdom should apply exactly the same amount of power as the power of that threat.

Power of a kingdom is defined as the summation of threats it can overcome. Each kingdom will face m distinct threats having powers ranging from 1 to m. 

Help Robert to arrange all the kingdoms in increasing order of their power.

Input Format

The first line contains an integer T  representing the number of kingdom.
For each test case, the first two line contains single integers n and m respectively,where n is number of cities in kingdom and m is maximum power threat.
The following n-1 lines each contains two integers ui and vi . It describes an edge between city ui and city vi .
The following n lines each contains an integer pi  represents the power of the i-th city.

Output Format

Print kingdom index and its power in increasing order.

Constraints

• 1<=T<=5
• 1<=n<=3000
• 1<=m<=100000
• 1<=ui,vi<=n
• 0<=wi<=10000