«Astra» هي لعبة لوحية جميلة يتناوب فيها اللاعبون على اكتشاف الكوكبات النجمية عن طريق تعليم النجوم. تجمع هذه اللعبة ببراعة بين التكتيك والاستراتيجية، مع مجموعة قواعد مبسطة وبديهية تجعلها سهلة التعلم وسريعة اللعب.

Photo by @kavics004 on BoardGameGeek

لنفترض وجود لعبة ثنائية بين أليس وبوب. في هذه اللعبة، توجد كوكبة على شكل شجرة، يمكن اعتبارها بياناً متصلاً يتكون من $n$ نجوم (مرقمة من $1$ إلى $n$) و $(n - 1)$ من الحواف. في البداية، يتم تعليم نجم واحد فقط $s$. يتناوب أليس وبوب على تعليم النجوم المتبقية وفقاً للقاعدة التالية:

• في كل دور، يجب على اللاعب تعليم نجم $1$ على الأقل و $k$ نجوم على الأكثر.
• يمكن تعليم كل نجم مرة واحدة فقط.
• لتكن $a_1, a_2, \cdots, a_p$ هي النجوم التي تم تعليمها في دور واحد، بترتيب تعليمها:
  • عند تعليم $a_1$، يجب أن يكون مجاوراً لنجم معلم بالفعل.
  • لكل $2 \le i \le p$، عند تعليم $a_i$، يجب أن يكون مجاوراً لـ $a_{i-1}$.

يكون النجمان $u$ و $v$ متجاورين إذا كانا متصلين مباشرة بحافة.

اللاعب الذي يعلم النجم الأخير يفوز بالكوكبة. علماً بأن أليس هي من تبدأ اللعب وأن كلا اللاعبين يلعبان بشكل أمثل، حدد لكل $1 \le s \le n$ من سيفوز بالكوكبة.

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 100$)، يشير إلى عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول على عددين صحيحين $n$ و $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$)، يشيران إلى عدد النجوم والحد الأقصى لعدد النجوم التي يتم تعليمها في كل دور.

في الأسطر الـ $(n - 1)$ التالية، يحتوي السطر الـ $i$ على عددين صحيحين $u_i$ و $v_i$ ($1 \le u_i, v_i \le n$)، مما يشير إلى وجود حافة تربط بين النجمين $u_i$ و $v_i$.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $2 \times 10^3$.

الإخراج

لكل حالة اختبار، اطبع سطراً واحداً يحتوي على سلسلة نصية $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$)، حيث يشير $d_i$ إلى من سيفوز بالكوكبة عندما يكون $s = i$. إذا كانت أليس ستفوز، فإن $d_i = 1$؛ وإلا، إذا كان بوب سيفوز، فإن $d_i = 0$.

مثال

الإدخال 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

الإخراج 1

011000
000
101

ملاحظة

حالة الاختبار الأولى في المثال موضحة أعلاه.

• لنأخذ $s = 1$. في الدور الأول، لدى أليس ثلاثة خيارات: تعليم $\{2\}$ أو $\{2, 3\}$ أو $\{2, 6\}$. إذا اختارت أليس $\{2, 6\}$، يمكن لبوب بعد ذلك تعليم $\{3\}$، وسيتبقى $2$ من النجوم المنفصلة. في الأدوار التالية، يمكن لكل لاعب تعليم نجم واحد فقط، وسيكون بوب هو الفائز. يمكن تحليل خيارات أليس الأخرى بنفس الطريقة.
• لنأخذ $s = 2$. في الدور الأول، لدى أليس خمسة خيارات: تعليم $\{1\}$ أو $\{3\}$ أو $\{6\}$ أو $\{3, 4\}$ أو $\{3, 5\}$. يمكن لأليس اختيار تعليم $\{3\}$، وسيتبقى $4$ نجوم منفصلة. في الأدوار التالية، يمكن لكل لاعب تعليم نجم واحد فقط، وستكون أليس هي الفائزة.

بالنسبة لحالة الاختبار الثانية في المثال، بما أن $k = 1$، فسيكون هناك بالضبط $3 - 1 = 2$ من الأدوار، لذلك سيكون بوب دائماً هو الفائز.

بالنسبة لحالة الاختبار الثالثة في المثال، إذا كان $s = 1$ أو $s = 3$، يمكن لأليس تعليم النجمين الـ $2$ المتبقيين مباشرة والفوز بالكوكبة.