״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$ הכוכבים הנותרים ולנצח בקבוצת הכוכבים.