446. Мега пицца

Не решаласьСложная

Группа из n n друзей решила совместно заказать огромную пиццу. Они готовятся выбирать топпинги из m m различных топпингов, доступных в пиццерии.

Сначала каждый друг говорит, какие топпинги он хотел бы видеть на пицце и какие он не хотел бы добавлять.

Требуется заказать такую пиццу, чтобы ни один друг не остался сильно разочарованным. Сильно разочарованным считается друг, у которого не учли два и более пожелания.

Помогите группе определить оптимальный план добавления топпингов или выяснить, что найти подходящую пиццу невозможно.

Формат ввода

В первой строке входных данных содержатся три целых числа n n , m m , k k — количество друзей, количество топпингов и количество пожеланий ( 1 ≤ n , m , k ≤ 100   000 1 \leq n, m, k \leq 100\,000 ).

В каждой из последующих k k строк содержатся по два целых числа a a и b b , обозначающих пожелания ( 1 ≤ a ≤ n , 1 ≤ ∣ b ∣ ≤ m 1 \leq a \leq n, 1 \leq |b| \leq m ). Если b > 0 b > 0 , то человек под номером a a хочет добавить топпинг под номером b b . Если же b < 0 b < 0 , то человек под номером a a не хочет добавлять топпинг под номером – b –b . Каждое пожелание указано во вводе не более одного раза, ни для кого из участников нет одновременно пожелания добавлять и не добавлять один и тот же топпинг.

Формат вывода

Если решения не существует, то выведите – 1 –1 .

Если иначе, в первой строке выходных данных выведите единственное целое число x x — количество топпингов, которые будут присутствовать в пицце.

Во второй строке выведите x x целых чисел — номера топпингов в пицце в произвольном порядке.

Если существует несколько возможных ответов, можно вывести любой из них. Обратите внимание, что не требуется искать максимальное или минимальное x x , можно вывести любой корректный ответ.

Примечание

В первом примере есть два друга. Первый друг хочет добавить в пиццу топпинг 2, а второй друг хочет добавить топпинг 1. Есть более одного варианта корректной пиццы. Например, можно сделать пиццу с обоими топпингами.

Ограничения

Ограничение времени
2 с
Ограничение памяти
512 МБ

Примеры

Пример 1

Ввод
2 2 2
1 2
2 1
Вывод
2
1 2 

Пример 2

Ввод
3 3 6
1 -1
1 2
2 -2
2 3
3 -3
3 1
Вывод
0

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти