Problem Description

The Hanged Man shows a man suspended from a t-shaped cross made out of living wood. The man is hanging upside-down, viewing the world from a completely different perspective. His facial expression is calm and serene, suggesting that he is in this hanging position by his own choice.

Bobo has two arrays $a_1$, $a_2$, . . . , $a_n$ and $b_1$, $b_2$, . . . , $b_n$. For each set $S$ $\subseteq$ {1, 2, . . . , $n$}, he denotes $A(S)$ = $\sum\limits_{i \subseteq S}$ $a_i$ and $B(S)$ = $\sum\limits_{i \subseteq S}$ $b_i$.
Bobo also has a tree of $n$ vertices conveniently labeled with 1, 2, . . . , $n$. A set $S$ $\subseteq$ {1, 2, . . . , $n$} is an independent set if and only if for any two vertices $u$ and $v$ connected directly on the tree, either $u$ $\notin$ $S$ or $v$ $\notin$ $S$ holds.
For each $x$ $\subseteq$ {1, 2, . . . , $m$}, Bobo would like to find f(x) which is the number of independnt set S with $A(S)$ = $x$ and $B(S)$ maximized.
Formally, f(x) = |{$S$ : $S$ $\subseteq$ $I$, $A(S)$ = $x$, $B(S)$ = $max^{A(T)=x}_{T \subseteq I}$ $B(T)$}| where $I$ stands for the family of the independent sets. Suppose there is no $A(S)$ = $x$ for some $i$, then $f(x)$ = 0.
Find out the value of f(1), f(2), . . . , f(m).

Input

The first line of the input contains one integer $T$ ≤ 20, denoting the number of testcases. Then $T$ testcases follows, separated with no extra blank lines.
The first line of each test case contains two integers $n$ and $m$.
The i-th of the following n lines contains two integers $a_i$ and $b_i$.
The i-th of the last (n - 1) lines contains two integers $u_i$ and $v_i$ which denotes an edge connected vertices $u_i$ and $v_i$.

Output

For each testcase, first print "Case $i$:" in one line ($i$ indicates the case number, starting from 1). In the line, print m integers which denote f(1), f(2), . . . , f(m).

3
3 2
1 1
1 1
1 1
1 2
1 3
4 5
1 1
2 2
3 2
2 1
1 2
2 3
3 4
5 10
3 1
2 2
4 4
7 8
5 16
1 2
1 3
2 4
2 5

Case 1:
3 1
Case 2:
1 1 2 2 0
Case 3:
0 1 1 1 1 1 1 1 1 1