Задача №1932. Дракончики
Петя занимается разведением дракончиков. У него есть \(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\) пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.
2 1 1 1 1 3 1 1
NO
2 2 1 1 1 3 1 2
YES 2 4