”Astra” är ett vackert brädspel där spelarna turas om att upptäcka stjärnbilder genom att markera stjärnorna. Detta spel är en smart blandning av taktik och strategi, med ett strömlinjeformat och intuitivt regelverk som gör det lätt att lära sig och snabbt att spela.

Photo by @kavics004 on BoardGameGeek

Betrakta ett spel för två spelare mellan Alice och Bob. I detta spel finns en trädformad stjärnbild, som kan betraktas som en sammanhängande graf bestående av $n$ stjärnor (numrerade från $1$ till $n$) och $(n - 1)$ kanter. I början är endast en stjärna $s$ markerad. Alice och Bob turas om att markera de återstående stjärnorna enligt följande regel:

• Varje tur måste en spelare markera minst $1$ stjärna och högst $k$ stjärnor.
• Varje stjärna kan endast markeras en gång.
• Låt $a_1, a_2, \cdots, a_p$ vara de stjärnor som markeras under en tur, i den ordning de markeras:
  • När $a_1$ markeras måste den vara granne med en redan markerad stjärna.
  • För alla $2 \le i \le p$, när $a_i$ markeras måste den vara granne med $a_{i-1}$.

Två stjärnor $u$ och $v$ är grannar om de är direkt förbundna med en kant.

Spelaren som markerar den sista stjärnan vinner stjärnbilden. Givet att Alice spelar först och att båda spelarna spelar optimalt, bestäm för varje $1 \le s \le n$ vem som kommer att vinna stjärnbilden.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$), som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $n$ och $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), som anger antalet stjärnor och det maximala antalet stjärnor som får markeras under varje tur.

För de följande $(n - 1)$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n$), vilket anger att det finns en kant som förbinder stjärnorna $u_i$ och $v_i$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^3$.

Utdata

För varje testfall, skriv ut en rad som innehåller en sträng $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), där $d_i$ anger vem som vinner stjärnbilden när $s = i$. Om Alice vinner är $d_i = 1$; annars, om Bob vinner, är $d_i = 0$.

Exempel

Indata 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

Anmärkning

Det första exempeltestfallet illustreras ovan.

• Betrakta $s = 1$. Under den första turen har Alice tre val: markera $\{2\}$, $\{2, 3\}$ eller $\{2, 6\}$. Om Alice väljer $\{2, 6\}$ kan Bob sedan markera $\{3\}$, och $2$ separerade stjärnor kommer att återstå. Under de följande turerna kan varje spelare bara markera en stjärna i taget, och Bob blir vinnaren. Alices övriga val kan analyseras på liknande sätt.
• Betrakta $s = 2$. Under den första turen har Alice fem val: markera $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ eller $\{3, 5\}$. Alice kan välja att markera $\{3\}$, och $4$ separerade stjärnor kommer att återstå. Under de följande turerna kan varje spelare bara markera en stjärna i taget, och Alice blir vinnaren.

För det andra exempeltestfallet, eftersom $k = 1$, kommer det att bli exakt $3 - 1 = 2$ turer, så Bob kommer alltid att vinna.

För det tredje exempeltestfallet, om $s = 1$ eller $s = 3$, kan Alice direkt markera de återstående $2$ stjärnorna och vinna stjärnbilden.