«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$ жұлдыздарын жалғайтын қабырға бар екенін білдіретін екі бүтін сан $u_i$ мен $v_i$ ($1 \le u_i, v_i \le n$) берілген.

Барлық тест жағдайлары бойынша $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$ жұлдызды бірден белгілеп, шоқжұлдызды ұтып ала алады.