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