# Safety in Treeland SOLUTIONS SAFETR

Page Contents

### Safety in Treeland SOLUTIONS SAFETR

The realm of Treeland comprises of N urban areas (numbered 1 through N) associated by N−1 bidirectional streets so that there is a way between each pair of urban areas.

So as to expand security in Treeland, the administration chose to set up police workplaces in K of its urban areas. For each substantial I, the I-th office is in city Vi and it has a range of proficiency Ri.

We should characterize the security level Si of every city I as follows:

At first, the security level of every city is equivalent to zero.

At that point, for each police office j that was fabricated (1≤j≤K), the security levels change in the accompanying way:

The security level of the city Vj increments by Rj.

The security levels of all urban communities at the separation 1 from Vj increment by Rj−1.

The security levels of all urban areas at the separation Rj−1 from Vj increment by 1.

Officially, for every city I, the j-th office expands the security level of this city by max(0,Rj−distance(i,Vj)).

Alice was responsible for ascertaining the new security levels of all urban communities after the workplaces were assembled. She previously completed her activity and saw an intriguing incident: for each substantial I, SVi=Ri holds. Presently she has provoked you to discover the security levels everything being equal.

Information

The primary line of the information contains a solitary whole number T signifying the quantity of experiments. The portrayal of T experiments follows.

The primary line of each experiment contains two space-isolated whole numbers N and K.

At that point, N−1 lines follow. Every one of these lines contains two space-isolated whole numbers u and v signifying that urban communities u and v are associated by a street.

K more lines follow. For each substantial I, the I-th of these lines contains two space-isolated whole numbers Vi and Ri.

Yield

For each experiment, print a solitary line containing N space-isolated numbers S1,S2,… ,SN.

Requirements

1≤T≤2,000

2≤N,K≤8⋅105

1≤u,v≤N

1≤Vi≤N for each legitimate I

V1,V2,… ,VK are pairwise particular

1≤Ri for each legitimate I

the whole of N over all experiments doesn’t surpass 8⋅105

Model Input

5 2

5 2

5 4

5 3

3 1

2 1

5 1

5 2

5 2

1 2

2 4

3 1

4 2

5 2

Model Output

0 1 0 1

0 2 0 2