Юкидің алдында біртүрлі жаяу жүргіншілер өткелі жатыр.

Бұл жаяу жүргіншілер өткелін $n$ төбесі бар ағаш ретінде қарастыруға болады. $i$-ші қыр $u_i$ төбесі мен $v_i$ төбесін қосады. Әрбір төбе қара немесе ақ түске боялған, ол ұзындығы $n$ болатын $s$ екілік жолымен сипатталады:

• Егер $s_i=0$ болса, $i$ төбесінің түсі қара.

• Егер $s_i=1$ болса, $i$ төбесінің түсі ақ.

Юкидің секіру қабілеті $k$-ға тең, бұл ол $x$ төбесінде тұрғанда $\operatorname{dist}(x,y)\le k$ болатындай кез келген $y$ төбесіне секіре алатынын білдіреді. Мұндағы $\operatorname{dist}(x,y)$ — $x$ төбесі мен $y$ төбесінің арасындағы қарапайым жолдағы қырлар саны.

Келесі кезекте Юки жаяу жүргіншілер өткелінде $n-1$ секіру раундын орындайды. $i$-ші раундта Юки $1$-ші төбеден бастап, секірулер тізбегі арқылы $i+1$-ші төбеге жеткісі келеді. Сонымен қатар, Юки секірулерден кейін қара төбеге қону санын барынша азайтқысы келеді.

Сіз Юкиге әрбір секіру раунды үшін қара төбеге қонудың ең аз санын табуға көмектесуіңіз керек.

Кіріс деректер

Бұл есеп бірнеше тест жиынтығынан тұрады.

Бірінші жолда тесттер санын білдіретін оң бүтін сан $t$ ($1\le t\le 10^5$) берілген.

Әрбір тест үшін:

• Бірінші жолда екі оң бүтін сан $n,k$ ($1\le n\le 5\cdot 10^5$, $1\le k\le n$) берілген.

• Екінші жолда ұзындығы $n$ болатын $s$ екілік жолы ($s_i\in\{0,1\}$) берілген.

• Келесі $n-1$ жолдың әрқайсысында екі оң бүтін сан $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$) берілген.

Барлық тесттер бойынша $n$ сандарының қосындысы $5\cdot 10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест үшін $n-1$ бүтін саннан тұратын бір жолды шығарыңыз, мұндағы $i$-ші бүтін сан $i$-ші секіру раунды кезінде Юкидің қара төбеге қонуының ең аз санын білдіреді.

Мысал

Кіріс деректер мысалы 1

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

Шығыс деректер мысалы 1

0 1 1 2
1 1 1 0 1 1 1 2

Ескертпе

Бірінші тест үшін:

• $1$-ші секіру раунды үшін барған төбелердің жарамды тізбектерінің бірі — $1,2$.

• $4$-ші секіру раунды үшін барған төбелердің жарамды тізбектерінің бірі — $1,3,5$.

Екінші тест үшін:

• $4$-ші секіру раунды үшін барған төбелердің жарамды тізбектерінің бірі — $1,5$.

• $7$-ші секіру раунды үшін барған төбелердің жарамды тізбектерінің бірі — $1,5,8$.

• $8$-ші секіру раунды үшін барған төбелердің жарамды тізбектерінің бірі — $1,4,9$.