"Astra" adalah permainan papan yang indah di mana para pemain bergiliran menemukan rasi bintang dengan menandai bintang-bintangnya. Permainan ini merupakan perpaduan cerdas antara taktik dan strategi, dengan aturan yang ringkas dan intuitif sehingga mudah dipelajari dan cepat dimainkan.

Photo by @kavics004 on BoardGameGeek

Tinjau sebuah permainan dua pemain antara Alice dan Bob. Dalam permainan ini, terdapat rasi bintang berbentuk pohon, yang dapat dianggap sebagai graf terhubung yang terdiri dari $n$ bintang (bernomor dari $1$ hingga $n$) dan $(n - 1)$ sisi. Pada awalnya, hanya satu bintang $s$ yang ditandai. Alice dan Bob bergiliran menandai bintang-bintang yang tersisa sesuai dengan aturan berikut:

• Setiap giliran, seorang pemain harus menandai setidaknya $1$ bintang dan paling banyak $k$ bintang.
• Setiap bintang hanya dapat ditandai satu kali.
• Misalkan $a_1, a_2, \cdots, a_p$ adalah bintang-bintang yang ditandai dalam satu giliran, sesuai urutan penandaannya:
  • Saat menandai $a_1$, bintang tersebut harus merupakan tetangga dari bintang yang sudah ditandai.
  • Untuk semua $2 \le i \le p$, saat menandai $a_i$, bintang tersebut harus merupakan tetangga dari $a_{i-1}$.

Dua bintang $u$ dan $v$ adalah tetangga jika keduanya terhubung langsung oleh sebuah sisi.

Pemain yang menandai bintang terakhir memenangkan rasi bintang tersebut. Diketahui bahwa Alice mendapat giliran pertama dan kedua pemain bermain secara optimal, untuk setiap $1 \le s \le n$, tentukan siapa yang akan memenangkan rasi bintang tersebut.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), yang menyatakan banyaknya bintang dan jumlah maksimum bintang yang dapat ditandai pada setiap giliran.

Untuk $(n - 1)$ baris berikutnya, baris ke-$i$ berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n$), yang menyatakan bahwa terdapat sisi yang menghubungkan bintang $u_i$ dan $v_i$.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \times 10^3$.

Keluaran

Untuk setiap kasus uji, cetak satu baris yang berisi sebuah string $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), di mana $d_i$ menyatakan siapa yang akan memenangkan rasi bintang ketika $s = i$. Jika Alice menang, maka $d_i = 1$; sebaliknya, jika Bob menang, maka $d_i = 0$.

Contoh

Masukan 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

Keluaran 1

011000
000
101

Catatan

Kasus uji contoh pertama diilustrasikan di atas.

• Tinjau $s = 1$. Pada giliran pertama, Alice memiliki tiga pilihan: menandai $\{2\}$, $\{2, 3\}$, atau $\{2, 6\}$. Jika Alice memilih $\{2, 6\}$, Bob kemudian dapat menandai $\{3\}$, dan akan tersisa $2$ bintang yang terpisah. Pada giliran-giliran berikutnya, setiap pemain hanya dapat menandai satu bintang, dan Bob akan menjadi pemenangnya. Pilihan Alice yang lain dapat dianalisis dengan cara serupa.
• Tinjau $s = 2$. Pada giliran pertama, Alice memiliki lima pilihan: menandai $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$, atau $\{3, 5\}$. Alice dapat memilih untuk menandai $\{3\}$, dan akan tersisa $4$ bintang yang terpisah. Pada giliran-giliran berikutnya, setiap pemain hanya dapat menandai satu bintang, dan Alice akan menjadi pemenangnya.

Untuk kasus uji contoh kedua, karena $k = 1$, akan ada tepat $3 - 1 = 2$ giliran, sehingga Bob akan selalu menjadi pemenangnya.

Untuk kasus uji contoh ketiga, jika $s = 1$ atau $s = 3$, Alice dapat langsung menandai $2$ bintang yang tersisa dan memenangkan rasi bintang tersebut.