„Astra” to piękna gra planszowa, w której gracze na zmianę odkrywają gwiazdozbiory, zaznaczając gwiazdy. Gra ta stanowi sprytne połączenie taktyki i strategii, a przejrzysty i intuicyjny zestaw zasad sprawia, że łatwo ją opanować i rozgrywka przebiega dynamicznie.

Photo by @kavics004 on BoardGameGeek

Rozważmy grę dwuosobową pomiędzy Alice i Bobem. W tej grze występuje gwiazdozbiór w kształcie drzewa, który można traktować jako spójny graf składający się z $n$ gwiazd (ponumerowanych od $1$ do $n$) oraz $(n - 1)$ krawędzi. Na początku zaznaczona jest tylko jedna gwiazda $s$. Alice i Bob na zmianę zaznaczają pozostałe gwiazdy zgodnie z następującą zasadą:

• W każdej turze gracz musi zaznaczyć co najmniej $1$ gwiazdę i co najwyżej $k$ gwiazd.
• Każda gwiazda może zostać zaznaczona tylko raz.
• Niech $a_1, a_2, \cdots, a_p$ oznaczają gwiazdy zaznaczone w danej turze, w kolejności ich zaznaczania:
  • Podczas zaznaczania $a_1$ musi ona być sąsiadem pewnej już zaznaczonej gwiazdy.
  • Dla wszystkich $2 \le i \le p$, podczas zaznaczania $a_i$ musi ona być sąsiadem $a_{i-1}$.

Dwie gwiazdy $u$ i $v$ są sąsiadami, jeśli są bezpośrednio połączone krawędzią.

Gracz, który zaznaczy ostatnią gwiazdę, zdobywa gwiazdozbiór. Zakładając, że Alice wykonuje pierwszy ruch i oboje gracze grają optymalnie, dla każdego $1 \le s \le n$ określ, kto zdobędzie gwiazdozbiór.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), oznaczające odpowiednio liczbę gwiazd oraz maksymalną liczbę gwiazd zaznaczanych w jednej turze.

W kolejnych $(n - 1)$ wierszach $i$-ty wiersz zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$), oznaczające, że istnieje krawędź łącząca gwiazdy $u_i$ oraz $v_i$.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^3$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający napis $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), gdzie $d_i$ określa, kto zdobędzie gwiazdozbiór dla $s = i$. Jeśli wygra Alice, to $d_i = 1$; w przeciwnym razie, jeśli wygra Bob, to $d_i = 0$.

Przykład

Wejście 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

Wyjście 1

011000
000
101

Uwaga

Pierwszy przykładowy przypadek testowy został zilustrowany powyżej.

• Rozważmy $s = 1$. W pierwszej turze Alice ma trzy możliwości: zaznaczyć $\{2\}$, $\{2, 3\}$ lub $\{2, 6\}$. Jeśli Alice wybierze $\{2, 6\}$, to Bob może następnie zaznaczyć $\{3\}$ i pozostaną $2$ rozdzielone gwiazdy. W kolejnych turach każdy gracz może zaznaczyć tylko po jednej gwieździe, więc zwycięzcą zostanie Bob. Pozostałe wybory Alice można przeanalizować analogicznie.
• Rozważmy $s = 2$. W pierwszej turze Alice ma pięć możliwości: zaznaczyć $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ lub $\{3, 5\}$. Alice może wybrać zaznaczenie $\{3\}$, dzięki czemu pozostaną $4$ rozdzielone gwiazdy. W kolejnych turach każdy gracz może zaznaczyć tylko po jednej gwieździe, więc zwyciężczynią zostanie Alice.

W drugim przykładowym przypadku testowym, ponieważ $k = 1$, odbędą się dokładnie $3 - 1 = 2$ tury, a zatem Bob zawsze będzie zwycięzcą.

W trzecim przykładowym przypadku testowym, jeśli $s = 1$ lub $s = 3$, Alice może od razu zaznaczyć pozostałe $2$ gwiazdy i zdobyć gwiazdozbiór.