« Astra » est un magnifique jeu de société dans lequel les joueurs découvrent à tour de rôle des constellations en marquant les étoiles. Ce jeu est un habile mélange de tactique et de stratégie, avec un ensemble de règles épuré et intuitif qui le rend facile à prendre en main et rapide à jouer.

Photo by @kavics004 on BoardGameGeek

Considérons un jeu à deux joueurs entre Alice et Bob. Dans ce jeu, il y a une constellation en forme d'arbre, qui peut être considérée comme un graphe connexe composé de $n$ étoiles (numérotées de $1$ à $n$) et de $(n - 1)$ arêtes. Au début, seule une étoile $s$ est marquée. Alice et Bob marquent à tour de rôle les étoiles restantes selon la règle suivante :

• À chaque tour, un joueur doit marquer au moins $1$ étoile et au plus $k$ étoiles.
• Chaque étoile ne peut être marquée qu'une seule fois.
• Soient $a_1, a_2, \cdots, a_p$ les étoiles marquées au cours d'un tour, dans l'ordre où elles sont marquées :
  • Lors du marquage de $a_1$, elle doit être voisine d'une étoile déjà marquée.
  • Pour tout $2 \le i \le p$, lors du marquage de $a_i$, elle doit être voisine de $a_{i-1}$.

Deux étoiles $u$ et $v$ sont voisines si elles sont directement reliées par une arête.

Le joueur qui marque la dernière étoile remporte la constellation. Sachant qu'Alice joue en premier et que les deux joueurs jouent de manière optimale, déterminez pour chaque $1 \le s \le n$ qui remportera la constellation.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$), indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), indiquant le nombre d'étoiles et le nombre maximum d'étoiles marquées à chaque tour.

Pour les $(n - 1)$ lignes suivantes, la $i$-ème ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$), indiquant qu'il existe une arête reliant les étoiles $u_i$ et $v_i$.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^3$.

Sortie

Pour chaque cas de test, affichez une ligne contenant une chaîne de caractères $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), où $d_i$ indique qui remportera la constellation lorsque $s = i$. Si Alice gagne, alors $d_i = 1$ ; sinon, si Bob gagne, alors $d_i = 0$.

Exemple

Entrée 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

Sortie 1

011000
000
101

Remarque

Le premier cas de test de l'exemple est illustré ci-dessus.

• Considérons $s = 1$. Au premier tour, Alice a trois choix : marquer $\{2\}$, $\{2, 3\}$ ou $\{2, 6\}$. Si Alice choisit $\{2, 6\}$, Bob peut alors marquer $\{3\}$, et il restera $2$ étoiles séparées. Pour les tours suivants, chaque joueur ne pourra marquer qu'une seule étoile, et Bob sera le vainqueur. Les autres choix d'Alice peuvent être analysés de la même manière.
• Considérons $s = 2$. Au premier tour, Alice a cinq choix : marquer $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ ou $\{3, 5\}$. Alice peut choisir de marquer $\{3\}$, et il restera $4$ étoiles séparées. Pour les tours suivants, chaque joueur ne pourra marquer qu'une seule étoile, et Alice sera la gagnante.

Pour le deuxième cas de test de l'exemple, comme $k = 1$, il y aura exactement $3 - 1 = 2$ tours, donc Bob sera toujours le vainqueur.

Pour le troisième cas de test de l'exemple, si $s = 1$ ou $s = 3$, Alice peut directement marquer les $2$ étoiles restantes et remporter la constellation.