Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Case

Задача Case

Як відомо, люди часто мають відразу декілька захоплень. Наприклад, одна і та ж людина може виступати на олімпіаді з програмування, грати в аматорському театрі і ходити в туристичні походи. Нехай кількість можливих захоплень дорівнює m і всі ці захоплення пронумеровані числами від 1 до  m. Гарантовано, що для кожного з m захоплень існує своя «група за інтересами», кожна людина належить хоча б до однієї з  груп і до кожної з m груп належить хоча б одна людина.
Одного дня Начальник-Забороняльник  вирішив, що m груп — забагато, призначив якийсь час "Ч" і велів зібратися представникам кожної групи в окремому обумовленому місці. Якщо на якомусь з обумовлених місць нікого не буде, Начальник-Забороняльник дасть собі волю і  заборонить відповідну групу. У такій ситуації не можна, щоб кожен діяв сам по собі, не радячись з іншими. Тому люди вирішили домовитися між собою. Зрозуміло, що ніхто не піде підтримувати групу, до якої не належить. Але кожен згоден вибирати одну зі своїх груп так, щоб жодна з груп не була заборонена. Напишіть програму, яка знайде спосіб розподілити людей по вказаних місцях Начальником-Забороняльником (або повідомить, що це неможливо). Достатньо досягти (якщо можливо), щоб на кожне місце прийшла хоч би одна людина. Якщо є декілька різних способів, які дозволяють врятувати всі групи від заборони, програма повинна вивести будь-який з їх.
Технічні умови. Программа читає з клавіатури кількість груп m (2 ≤ m ≤ 150), кількість людей n (m ≤ n ≤ 200), далі n блоків такої структури: перше число блоку Кі - кількість  груп, до якої належить і-й людина (1 ≤ Кі ≤ m) потім задано Кі  номерів тих груп, до яких він належить (в порядку зростання). Всі вхідні дані записані в одному рядку через пропуски.  Начальник-Забороняльник не належить до жодної з m груп і не є жодним із згаданих людей.
Програма повинна вивести на екран спочатку  відповідь 1, якщо зберегти  всі групи можна, або 0 якщо ні. В разі відповіді 1 далі потрібно вивести в тому ж рядку  n чисел (значенням від 1 до m кожне), які позначають, на збори якої групи піде відповідний (1-а, 2-а ..., n-а) людина. Якщо є декілька різних розподілів, які дають можливість врятувати всі групи від заборони, виводьте будь-який.

Приклади

Введення
3 3 1 1 1 1 2 2 3

Виведення
0

Введення
3 4 1 1 2 2 3 1 3 2 1 3

Виведення
1 1 2 3 1


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"