eolymp
bolt
Try our new interface for solving problems
Məsələlər

Конкурс пар

Конкурс пар

Конкурс пар? Как так, мы же не планировали проводить его в эту смену! Ну что ж, раз директор сказала "надо", значит надо. До полдника мы успели обойти весь лагерь и попросили каждую девочку написать список всех мальчиков, с которыми она готова участвовать в конкурсе. Как же нам выбрать пары, которые будут принимать участие в конкурсе? После долгих споров, мы решили, что пары можно составить как угодно, главное - не обидеть девочек. Девочка обидится в том случае, если мы не пригласим ее на конкурс, при этом в ее списке будет мальчик, которого мы тоже не пригласим. Тогда она просто не поймет, почему ее не позвали участвовать, ведь этот мальчик все равно не занят ни в одной паре. Помогите нам составить список пар таким образом, чтобы ни одна девочка не обиделась. \InputFile В первой строке через пробел записаны числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100}) - количество девочек и мальчиков в лагере, соответственно. В \textbf{i}-й из следующих \textbf{n} строк задается список \textbf{i}-й девочки. Список начинается с числа \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{m}) - количества мальчиков, с которыми эта девочка хочет участвовать в конкурсе. Затем следует \textbf{k} чисел - номера этих мальчиков. Мальчики занумерованы числами от \textbf{1} до \textbf{m}. Все числа в строке разделены пробелами. \OutputFile В первой строке выведите число \textbf{c} - количество пар, которые нам нужно позвать на конкурс. В каждой из следующих \textbf{c} строк выведите через пробел номер девочки и мальчика, составляющих очередную пару. Пары можно выводить в любом порядке. Если есть несколько способов составить список пар, выведите любой из них. Если мы не сможем добиться того, чтобы ни одна девочка не обиделась, выведите "\textbf{-1}".
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
2 2
2 1 2
1 2
Çıxış verilənləri #1
2
1 1
2 2