”Astra” on kaunis lautapeli, jossa pelaajat löytävät vuorotellen tähdistöjä merkitsemällä tähtiä. Peli on nokkela yhdistelmä taktiikkaa ja strategiaa, ja sen virtaviivainen ja intuitiivinen sääntökokoelma tekee siitä helposti opittavan ja nopean pelata.

Photo by @kavics004 on BoardGameGeek

Tarkastellaan kahden pelaajan peliä Alicen ja Bobin välillä. Tässä pelissä on puun muotoinen tähdistö, jota voidaan pitää yhtenäisenä verkkona, joka koostuu $n$ tähdestä (numeroitu $1$:stä $n$:ään) ja $(n - 1)$ kaaresta. Alussa vain yksi tähti $s$ on merkitty. Alice ja Bob merkitsevät vuorotellen jäljellä olevia tähtiä seuraavan säännön mukaisesti:

• Jokaisella vuorolla pelaajan tulee merkitä vähintään $1$ tähti ja enintään $k$ tähteä.
• Jokaisen tähden voi merkitä vain kerran.
• Olkoot $a_1, a_2, \cdots, a_p$ yhdellä vuorolla merkityt tähdet siinä järjestyksessä kuin ne merkitään:
  • Kun tähti $a_1$ merkitään, sen täytyy olla jonkin jo merkityn tähden naapuri.
  • Kaikilla $2 \le i \le p$, kun tähti $a_i$ merkitään, sen täytyy olla tähden $a_{i-1}$ naapuri.

Kaksi tähteä $u$ ja $v$ ovat naapureita, jos niitä yhdistää suoraan kaari.

Pelaaja, joka merkitsee viimeisen tähden, voittaa tähdistön. Kun tiedetään, että Alice pelaa ensin ja molemmat pelaajat pelaavat optimaalisesti, määritä jokaiselle $1 \le s \le n$, kumpi voittaa tähdistön.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), joka ilmaisee testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), jotka ilmaisevat tähtien lukumäärän ja yhdellä vuorolla merkittävien tähtien enimmäismäärän.

Seuraavilla $(n - 1)$ rivillä $i$:s rivi sisältää kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n$), mikä ilmaisee, että tähtien $u_i$ ja $v_i$ välillä on kaari.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^3$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää merkkijonon $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), missä $d_i$ ilmaisee, kumpi voittaa tähdistön, kun $s = i$. Jos Alice voittaa, niin $d_i = 1$; muussa tapauksessa, jos Bob voittaa, niin $d_i = 0$.

Esimerkki

Syöte 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

Tuloste 1

011000
000
101

Huomautus

Ensimmäinen esimerkkitestitapaus on havainnollistettu yllä.

• Tarkastellaan tapausta $s = 1$. Ensimmäisellä vuorolla Alicella on kolme vaihtoehtoa: merkitä $\{2\}$, $\{2, 3\}$ tai $\{2, 6\}$. Jos Alice valitsee $\{2, 6\}$, Bob voi sen jälkeen merkitä $\{3\}$, jolloin jäljelle jää $2$ erillistä tähteä. Seuraavilla vuoroilla kumpikin pelaaja voi merkitä vain yhden tähden, joten Bob voittaa. Alicen muut vaihtoehdot voidaan analysoida vastaavasti.
• Tarkastellaan tapausta $s = 2$. Ensimmäisellä vuorolla Alicella on viisi vaihtoehtoa: merkitä $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ tai $\{3, 5\}$. Alice voi valita merkitsevänsä $\{3\}$, jolloin jäljelle jää $4$ erillistä tähteä. Seuraavilla vuoroilla kumpikin pelaaja voi merkitä vain yhden tähden, joten Alice voittaa.

Toisessa esimerkkitestitapauksessa, koska $k = 1$, vuoroja on täsmälleen $3 - 1 = 2$, joten Bob voittaa aina.

Kolmannessa esimerkkitestitapauksessa, jos $s = 1$ tai $s = 3$, Alice voi suoraan merkitä jäljellä olevat $2$ tähteä ja voittaa tähdistön.