4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс, Актобе

Есеп C. Маглдар шабуылдайды

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Әлемдік ғаламтор $n$ шыңдармен және $n - 1$ қабырғаларынан құралады. Әр қабырға екі басқа-басқа шыңдарды жалғайды. Осы желіде кез-келген шыңнан басқа шыңдардың барлығына қабырғалар арқылы жетуге болады. Әр шың басында Сиқыршы тұрады. Сиқыршылар — өте жылы шырайлы жаратылыстар, дегенмен, олар тек жұптасып өмір сүре алады. 2 Сиқыршы көршілес шыңдарда тұрғанда ғана жұп құра алады. Әр Сиқыршы тек бір ғана жұп құра алады. Маглдар кейбір шыңдарды бұғаттап, сонымен қатар бұғатталған шыңдардағы Сиқыршыларды да қолға түсіруді шешті. Әр бұғаттау желінің $k$ бұғатталатын шыңдарынан тұрады. Әр бұғатталған шыңнан Маглар сол шыңдағы Сиқыршыны қолға түсіріп, алып кетеді. Бұғаттан кейін байбалам басталап, Сиқыршылар өзіне жұп ізестіреді. Егерде ең болмаса бір Сиқыршы өзіне жұп таба алмаса, Хаос орнайды. Назар аударыңыз, Сиқыршылар жұптар саны көп болатындай, жұптарға бөлінеді. Сиқыршыларда ықтимал бұғаттардың $q$ болжамдары бар. Әр болжам үшін, сол болжам орындалса Хаос орнайтынын анықтаңыз.

Формат входного файла

Бірінші жолда екі сан $n$, $q$ ($1 <= n, q <= 5*10^5$) — шыңдар саны мен болжамдар саны берілген. Келесі $n-1$ жолда екі сан $u$, $v$ ($1 <= u, v <= n$) — арасында қабырғалары бар шыңдар берілген. Келесі $q$ жолда болжамдар берілген. Әр болжам $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ түрінде — бұғатталған шыңдардың саны мен нөмерлері беріледі.

Формат выходного файла

Бос жермен бөлінген $q$ сан шығарыңыз. Әр бұғат үшін келген болжамдар ретінде, егер Сиқыршылар бір-біріне жұп таба алса $1$ (Хаос орнамаса), таба алмаса $0$ (Хаос орнаса) шығарыңыз.

Система оценки

$sum(k)$ деген барлық болжамдардағы бұғатталған шыңдардың саны. Есеп 5 бөлімнен тұрады: 1. $1 <= n, q, sum(k) <= 3000$, 2 ден көп шыңмен жалғанған шың жоқ. Бөлім $13$ ұпайға бағаланады. 2. $1 <= n, q, sum(k) <= 3000$. Бөлім $17$ ұпайға бағаланады. 3. $1 <= n, q, sum(k) <= 100000$. Бөлім $22$ ұпайға бағаланады. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Бөлім $19$ ұпайға бағаланады. 5. $1 <= n, q, sum(k) <= 500000$. Бөлім $29$ ұпайға бағаланады.

Пример:

Вход

3 3
1 2
2 3
1 1
1 2
1 3

Ответ

1 0 1

( Aidos Nurmash )