"Astra" là một trò chơi cờ bàn tuyệt đẹp, nơi người chơi lần lượt khám phá các chòm sao bằng cách đánh dấu các ngôi sao. Trò chơi này là sự kết hợp khéo léo giữa chiến thuật và chiến lược, với bộ quy tắc tinh gọn và trực quan giúp người chơi dễ dàng nắm bắt và chơi nhanh.

Photo by @kavics004 on BoardGameGeek

Xét một trò chơi hai người giữa Alice và Bob. Trong trò chơi này, có một chòm sao hình cây, có thể được coi là một đồ thị liên thông gồm $n$ ngôi sao (được đánh số từ $1$ đến $n$) và $(n - 1)$ cạnh. Ban đầu, chỉ có một ngôi sao $s$ được đánh dấu. Alice và Bob lần lượt đánh dấu các ngôi sao còn lại theo quy tắc sau:

• Mỗi lượt, một người chơi phải đánh dấu ít nhất $1$ ngôi sao và nhiều nhất $k$ ngôi sao.
• Mỗi ngôi sao chỉ có thể được đánh dấu một lần.
• Gọi $a_1, a_2, \cdots, a_p$ là các ngôi sao được đánh dấu trong một lượt, theo thứ tự chúng được đánh dấu:
  • Khi đánh dấu $a_1$, nó phải là hàng xóm của một ngôi sao đã được đánh dấu.
  • Với mọi $2 \le i \le p$, khi đánh dấu $a_i$, nó phải là hàng xóm của $a_{i-1}$.

Hai ngôi sao $u$ và $v$ là hàng xóm nếu chúng được nối trực tiếp với nhau bởi một cạnh.

Người chơi đánh dấu ngôi sao cuối cùng sẽ giành chiến thắng chòm sao đó. Biết rằng Alice là người đi trước và cả hai người chơi đều chơi tối ưu, với mỗi $1 \le s \le n$, hãy xác định xem ai sẽ thắng chòm sao đó.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 100$), cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$), cho biết số lượng ngôi sao và số lượng ngôi sao tối đa được đánh dấu trong mỗi lượt.

Trong $(n - 1)$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$), cho biết có một cạnh nối ngôi sao $u_i$ và $v_i$.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^3$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa một xâu $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$), trong đó $d_i$ cho biết ai sẽ thắng chòm sao khi $s = i$. Nếu Alice thắng thì $d_i = 1$; ngược lại, nếu Bob thắng thì $d_i = 0$.

Ví dụ

Dữ liệu vào 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

Kết quả 1

011000
000
101

Giải thích

Bộ dữ liệu mẫu đầu tiên được minh họa ở hình trên.

• Xét $s = 1$. Ở lượt đầu tiên, Alice có ba lựa chọn: đánh dấu $\{2\}$, $\{2, 3\}$, hoặc $\{2, 6\}$. Nếu Alice chọn $\{2, 6\}$, Bob sau đó có thể đánh dấu $\{3\}$, và sẽ còn lại $2$ ngôi sao tách biệt. Trong các lượt tiếp theo, mỗi người chơi chỉ có thể đánh dấu một ngôi sao, và Bob sẽ là người chiến thắng. Các lựa chọn khác của Alice có thể được phân tích tương tự.
• Xét $s = 2$. Ở lượt đầu tiên, Alice có năm lựa chọn: đánh dấu $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$, hoặc $\{3, 5\}$. Alice có thể chọn đánh dấu $\{3\}$, và sẽ còn lại $4$ ngôi sao tách biệt. Trong các lượt tiếp theo, mỗi người chơi chỉ có thể đánh dấu một ngôi sao, và Alice sẽ là người chiến thắng.

Đối với bộ dữ liệu mẫu thứ hai, vì $k = 1$, sẽ có đúng $3 - 1 = 2$ lượt, vì vậy Bob sẽ luôn là người chiến thắng.

Đối với bộ dữ liệu mẫu thứ ba, nếu $s = 1$ hoặc $s = 3$, Alice có thể đánh dấu trực tiếp $2$ ngôi sao còn lại và giành chiến thắng chòm sao.