«Astra» es un hermoso juego de mesa en el que los jugadores se turnan para descubrir constelaciones marcando las estrellas. Este juego es una ingeniosa mezcla de táctica y estrategia, con un conjunto de reglas ágil e intuitivo que hace que sea fácil de aprender y rápido de jugar.

Photo by @kavics004 on BoardGameGeek

Considere un juego de dos jugadores entre Alice y Bob. En este juego, hay una constelación con forma de árbol, que puede considerarse como un grafo conexo que consta de $n$ estrellas (numeradas de $1$ a $n$) y $(n - 1)$ aristas. Al principio, solo una estrella $s$ está marcada. Alice y Bob se turnan para marcar las estrellas restantes según la siguiente regla:

• En cada turno, un jugador debe marcar al menos $1$ estrella y como máximo $k$ estrellas.
• Cada estrella solo puede marcarse una vez.
• Sean $a_1, a_2, \cdots, a_p$ las estrellas marcadas en un turno, en el orden en que se marcan:
  • Al marcar $a_1$, debe ser vecina de una estrella ya marcada.
  • Para todo $2 \le i \le p$, al marcar $a_i$, debe ser vecina de $a_{i-1}$.

Dos estrellas $u$ y $v$ son vecinas si están conectadas directamente por una arista.

El jugador que marca la última estrella gana la constelación. Dado que Alice es la primera en jugar y ambos jugadores juegan de manera óptima, para cada $1 \le s \le n$, determine quién ganará la constelación.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$), que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), que indican el número de estrellas y el número máximo de estrellas marcadas en cada turno.

En las siguientes $(n - 1)$ líneas, la $i$-ésima línea contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n$), que indican que hay una arista que conecta las estrellas $u_i$ y $v_i$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^3$.

Salida

Para cada caso de prueba, imprima una línea que contenga una cadena $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), donde $d_i$ indica quién ganará la constelación cuando $s = i$. Si Alice gana, entonces $d_i = 1$; de lo contrario, si Bob gana, entonces $d_i = 0$.

Ejemplo

Entrada 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

Salida 1

011000
000
101

Nota

El primer caso de prueba de ejemplo se ilustra arriba.

• Considere $s = 1$. En el primer turno, Alice tiene tres opciones: marcar $\{2\}$, $\{2, 3\}$ o $\{2, 6\}$. Si Alice elige $\{2, 6\}$, Bob puede entonces marcar $\{3\}$, y quedarán $2$ estrellas separadas. En los turnos siguientes, cada jugador solo podrá marcar una estrella, y Bob será el ganador. Las otras opciones de Alice pueden analizarse de manera similar.
• Considere $s = 2$. En el primer turno, Alice tiene cinco opciones: marcar $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ o $\{3, 5\}$. Alice puede elegir marcar $\{3\}$, y quedarán $4$ estrellas separadas. En los turnos siguientes, cada jugador solo podrá marcar una estrella, y Alice será la ganadora.

Para el segundo caso de prueba de ejemplo, como $k = 1$, habrá exactamente $3 - 1 = 2$ turnos, por lo que Bob siempre será el ganador.

Para el tercer caso de prueba de ejemplo, si $s = 1$ o $s = 3$, Alice puede marcar directamente las $2$ estrellas restantes y ganar la constelación.