The first line contains two integers N and K (0≤K≤N), respectively the number of barns on the farm

and the number of barns that have already been painted.

The next N-1lines each contain two integers xx and yy (1≤x,y≤N,x≠y) describing a path directly connecting barns x and y.

The next K lines each contain two integers bb and cc (1≤b≤N, 1≤c≤3) indicating that barn bb is painted with color c.