Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex
Информационная поддержка:
журнал "Мир ПК"
IV Открытая олимпиада школьников по программированию, 2009/10 учебный год
Задача C. Дракончики
| Имя входного файла: | c.in |
| Имя выходного файла: | c.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Петя занимается разведением дракончиков. У него есть M зеленых дракончиков и K желтых. У Пети есть N двухместных аквариумов для дракончиков и M+K-2N одноместных.
Петя, понаблюдав некоторое время за своими дракончиками, установил, что некоторые пары дракончиков не могут жить вместе (будучи помещенными в один аквариум они тут же начинают драться), а также некоторые дракончики совершенно не переносят одиночества и поэтому не могут жить в одноместном аквариуме.
Петя хочет с использованием своих знаний так разместить дракончиков по аквариумам, чтобы в каждом двухместном аквариуме обязательно был один зеленый дракончик и один желтый, и при этом драконы, не переносящие одиночества, обязательно были бы помещены в двухместный аквариум, и в двухместном аквариуме никогда не оказывалось бы двух драконов, которые не могут жить вместе.
Формат входных данных
Вводятся числа M, K, N (M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200). Будем считать, что зеленые дракончики пронумерованы числами от 1 до M, а желтые - числами от M+1 до M+K.
Далее идет число T (0 ≤ T ≤ MK) - количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет T пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе - желтого). Далее идет число Q (0 ≤ Q ≤ M + K)- количество дракончиков, не переносящих одиночества. Далее идет Q чисел, задающих номера этих драконов.
Формат выходных данных
В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие N строк выведите N пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.
Примеры
| c.in | c.out |
2 1 1 1 1 3 1 1 |
NO |
2 2 1 1 1 3 1 2 |
YES 2 4 |