„Astra“ ist ein wunderschönes Brettspiel, bei dem die Spieler abwechselnd Sternbilder entdecken, indem sie die Sterne markieren. Dieses Spiel ist eine clevere Mischung aus Taktik und Strategie, mit einem schlanken und intuitiven Regelwerk, durch das es leicht zu erlernen und schnell zu spielen ist.

Photo by @kavics004 on BoardGameGeek

Betrachten Sie ein Zwei-Spieler-Spiel zwischen Alice und Bob. In diesem Spiel gibt es ein baumförmiges Sternbild, das als zusammenhängender Graph bestehend aus $n$ Sternen (nummeriert von $1$ bis $n$) und $(n - 1)$ Kanten betrachtet werden kann. Zu Beginn ist nur ein einziger Stern $s$ markiert. Alice und Bob markieren abwechselnd die verbleibenden Sterne nach folgender Regel:

• In jedem Zug muss ein Spieler mindestens $1$ Stern und höchstens $k$ Sterne markieren.
• Jeder Stern kann nur einmal markiert werden.
• Seien $a_1, a_2, \cdots, a_p$ die in einem Zug markierten Sterne in der Reihenfolge, in der sie markiert werden:
  • Beim Markieren von $a_1$ muss dieser ein Nachbar eines bereits markierten Sterns sein.
  • Für alle $2 \le i \le p$ muss beim Markieren von $a_i$ dieser ein Nachbar von $a_{i-1}$ sein.

Zwei Sterne $u$ und $v$ sind Nachbarn, wenn sie direkt durch eine Kante verbunden sind.

Der Spieler, der den letzten Stern markiert, gewinnt das Sternbild. Da Alice am Zug beginnt und beide Spieler optimal spielen, bestimmen Sie für jedes $1 \le s \le n$, wer das Sternbild gewinnen wird.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die die Anzahl der Testfälle angibt. Für jeden Testfall:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), die die Anzahl der Sterne und die maximale Anzahl der in jedem Zug markierten Sterne angeben.

In den folgenden $(n - 1)$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$), was angibt, dass es eine Kante gibt, die die Sterne $u_i$ und $v_i$ verbindet.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^3$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer Zeichenkette $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$) aus, wobei $d_i$ angibt, wer das Sternbild gewinnt, wenn $s = i$ ist. Wenn Alice gewinnt, ist $d_i = 1$; andernfalls, wenn Bob gewinnt, ist $d_i = 0$.

Beispiel

Eingabe 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

Ausgabe 1

011000
000
101

Hinweis

Der erste Beispiel-Testfall ist oben dargestellt.

• Betrachten Sie $s = 1$. Im ersten Zug hat Alice drei Möglichkeiten: $\{2\}$, $\{2, 3\}$ oder $\{2, 6\}$ zu markieren. Wenn Alice $\{2, 6\}$ wählt, kann Bob anschließend $\{3\}$ markieren, und es bleiben $2$ getrennte Sterne übrig. In den folgenden Zügen kann jeder Spieler nur jeweils einen Stern markieren, und Bob wird der Gewinner sein. Alices andere Möglichkeiten können auf ähnliche Weise analysiert werden.
• Betrachten Sie $s = 2$. Im ersten Zug hat Alice fünf Möglichkeiten: $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$ oder $\{3, 5\}$ zu markieren. Alice kann wählen, $\{3\}$ zu markieren, und es bleiben $4$ getrennte Sterne übrig. In den folgenden Zügen kann jeder Spieler nur jeweils einen Stern markieren, und Alice wird die Gewinnerin sein.

Im zweiten Beispiel-Testfall gibt es wegen $k = 1$ genau $3 - 1 = 2$ Züge, sodass Bob immer der Gewinner ist.

Im dritten Beispiel-Testfall kann Alice, falls $s = 1$ oder $s = 3$ ist, direkt die verbleibenden $2$ Sterne markieren und das Sternbild gewinnen.