«Astra» er et vakkert brettspill der spillerne bytter på å oppdage stjernebilder ved å markere stjernene. Dette spillet er en smart blanding av taktikk og strategi, med et strømlinjeformet og intuitivt regelsett som gjør det lett å lære og raskt å spille.

Photo by @kavics004 on BoardGameGeek

Betrakt et tospillerspill mellom Alice og Bob. I dette spillet er det et treformet stjernebilde, som kan betraktes som en sammenhengende graf bestående av $n$ stjerner (nummerert fra $1$ til $n$) og $(n - 1)$ kanter. Til å begynne med er bare én stjerne $s$ markert. Alice og Bob bytter på å markere de gjenværende stjernene etter følgende regel:

• Hver tur må en spiller markere minst $1$ stjerne og høyst $k$ stjerner.
• Hver stjerne kan bare markeres én gang.
• La $a_1, a_2, \cdots, a_p$ være stjernene som markeres i løpet av en tur, i den rekkefølgen de markeres:
  • Når $a_1$ markeres, må den være nabo til en allerede markert stjerne.
  • For alle $2 \le i \le p$, når $a_i$ markeres, må den være nabo til $a_{i-1}$.

To stjerner $u$ og $v$ er naboer hvis de er direkte forbundet med en kant.

Spilleren som markerer den siste stjernen, vinner stjernebildet. Gitt at Alice spiller først og at begge spillerne spiller optimalt, bestem for hver $1 \le s \le n$ hvem som vil vinne stjernebildet.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 100$), som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder to heltall $n$ og $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), som angir antallet stjerner og det maksimale antallet stjerner som kan markeres i hver tur.

For de følgende $(n - 1)$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), som angir at det er en kant som forbinder stjernene $u_i$ og $v_i$.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^3$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder en streng $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), der $d_i$ angir hvem som vil vinne stjernebildet når $s = i$. Hvis Alice vinner, er $d_i = 1$; ellers, hvis Bob vinner, er $d_i = 0$.

Eksempel

Inndata 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

Utdata 1

011000
000
101

Merk

Det første eksempeltesttilfellet er illustrert ovenfor.

• Betrakt $s = 1$. I første tur har Alice tre valg: markere $\{2\}$, $\{2, 3\}$ eller $\{2, 6\}$. Hvis Alice velger $\{2, 6\}$, kan Bob deretter markere $\{3\}$, og $2$ adskilte stjerner vil gjenstå. I de påfølgende turene kan hver spiller bare markere én stjerne, og Bob vil bli vinneren. Alices andre valg kan analyseres på tilsvarende måte.
• Betrakt $s = 2$. I første tur har Alice fem valg: markere $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ eller $\{3, 5\}$. Alice kan velge å markere $\{3\}$, og $4$ adskilte stjerner vil gjenstå. I de påfølgende turene kan hver spiller bare markere én stjerne, og Alice vil bli vinneren.

For det andre eksempeltesttilfellet, ettersom $k = 1$, vil det være nøyaktig $3 - 1 = 2$ turer, så Bob vil alltid være vinneren.

For det tredje eksempeltesttilfellet, hvis $s = 1$ eller $s = 3$, kan Alice direkte markere de gjenværende $2$ stjernene og vinne stjernebildet.