«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$ зірки й виграти сузір'я.