„Astra“ er fallegt borðspil þar sem leikmenn skiptast á að uppgötva stjörnumerki með því að merkja stjörnurnar. Þetta spil er snjöll blanda af taktík og herkænsku, með straumlínulöguðum og innsæisríkum reglum sem gera það auðvelt að læra og fljótlegt að spila.

Photo by @kavics004 on BoardGameGeek

Lítum á tveggja manna leik milli Alice og Bob. Í þessum leik er trélaga stjörnumerki, sem líta má á sem samanhangandi net sem samanstendur af $n$ stjörnum (númeruðum frá $1$ til $n$) og $(n - 1)$ leggjum. Í upphafi er aðeins ein stjarna $s$ merkt. Alice og Bob skiptast á að merkja stjörnurnar sem eftir eru samkvæmt eftirfarandi reglu:

• Í hverri umferð verður leikmaður að merkja að minnsta kosti $1$ stjörnu og að hámarki $k$ stjörnur.
• Hverja stjörnu má aðeins merkja einu sinni.
• Látum $a_1, a_2, \cdots, a_p$ vera stjörnurnar sem merktar eru í einni umferð, í þeirri röð sem þær eru merktar:
  • Þegar $a_1$ er merkt verður hún að vera nágranni stjörnu sem þegar hefur verið merkt.
  • Fyrir öll $2 \le i \le p$, þegar $a_i$ er merkt verður hún að vera nágranni $a_{i-1}$.

Tvær stjörnur $u$ og $v$ eru nágrannar ef þær eru beintengdar með legg.

Leikmaðurinn sem merkir síðustu stjörnuna vinnur stjörnumerkið. Gefið að Alice geri fyrst og báðir leikmenn spili ákjósanlega, ákvarðið fyrir hvert $1 \le s \le n$ hvor mun vinna stjörnumerkið.

Inntak

Það eru margir prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 100$), sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), sem gefa til kynna fjölda stjarna og hámarksfjölda stjarna sem merktar eru í hverri umferð.

Í næstu $(n - 1)$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), sem gefur til kynna að leggur tengi stjörnurnar $u_i$ og $v_i$.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^3$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur streng $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), þar sem $d_i$ gefur til kynna hvor mun vinna stjörnumerkið þegar $s = i$. Ef Alice vinnur, þá er $d_i = 1$; annars, ef Bob vinnur, þá er $d_i = 0$.

Dæmi

Inntak 1

3
6 2
1 2
3 2
3 4
5 3
2 6
3 1
1 2
2 3
3 2
1 2
2 3

Úttak 1

011000
000
101

Athugasemd

Fyrsta prófunartilvikið í dæminu er sýnt hér að ofan.

• Skoðum $s = 1$. Í fyrstu umferð hefur Alice þrjá valkosti: að merkja $\{2\}$, $\{2, 3\}$ eða $\{2, 6\}$. Ef Alice velur $\{2, 6\}$ getur Bob síðan merkt $\{3\}$, og þá verða $2$ aðskildar stjörnur eftir. Í næstu umferðum getur hvor leikmaður aðeins merkt eina stjörnu í einu, og Bob verður sigurvegarinn. Hina valkosti Alice má greina á svipaðan hátt.
• Skoðum $s = 2$. Í fyrstu umferð hefur Alice fimm valkosti: að merkja $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ eða $\{3, 5\}$. Alice getur valið að merkja $\{3\}$, og þá verða $4$ aðskildar stjörnur eftir. Í næstu umferðum getur hvor leikmaður aðeins merkt eina stjörnu í einu, og Alice verður sigurvegarinn.

Fyrir annað prófunartilvikið í dæminu, þar sem $k = 1$, verða nákvæmlega $3 - 1 = 2$ umferðir, þannig að Bob verður alltaf sigurvegarinn.

Fyrir þriðja prófunartilvikið í dæminu, ef $s = 1$ eða $s = 3$, getur Alice merkt remaining $2$ stjörnurnar beint og unnið stjörnumerkið.