eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Надежная безопасность

Надежная безопасность

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Алиса и Боб получили карту секретного подземного объекта. Объект состоит из n подразделений безопасности и m химических лабораторий, соединенных двунаправленными туннелями. Карта этого объекта образует дерево: ровно n + m - 1 туннелей, циклов нет. Вершины, соответствующие подразделениям безопасности, имеют номера от 1 до n, химические лаборатории имеют номера от n + 1 до n + m. Каждый туннель соединяет блок безопасности с химической лабораторией; нет туннелей между двумя подразделениями охраны или двумя химическими лабораториями.

На случай, если Алису или Боба поймают, они решили разделить карту на две части. Для этого они вычислили код Прюфера дерева. Затем Алиса сохранила некоторые числа между 1 и n в своем хранилище данных в том же порядке, в котором они идут в исходном коде, а Боб сохранил некоторые числа от n + 1 до n + m в его хранилище таким же образом.

Код Прюфера для дерева из k вершин представляет собой последовательность k - 2 целых чисел от 1 до k, построенную следующим образом. Найдите лист (вершину степени один) с наименьшим номером, удалите его из дерева, затем выведите номер его единственного соседа. Повторите эту операцию еще k - 3 раза, пока не останется только одно ребро. Выведенная последовательность из k - 2 номеров вершин является кодом Прюфера.

Алиса и Боб благополучно вернулись и готовы объединить свои данные, чтобы восстановить исходную карту. Они могут ошибиться во время резервного копирования, означающее что такой карты не существует. Алисе и Бобу нужна Ваша помощь, чтобы восстановить любую возможную карту объекта в соответствии с собранными данными, чтобы части Алисы и Боба были подпоследовательностями кода Прюфера карты.

Вхідні дані

Первая строка содержит четыре целых числа n, m, k_a и k_b~(2 \le n, m \le 10^5, 1 \le k_a, k_b, k_a + k_b \le n + m - 2).

Вторая строка содержит k_a целых чисел a_1, a_2, ..., a_{k_a}~(1 \le a_i \le n) — часть карты Алисы.

Третья строка содержит k_b целых чисел b_1, b_2, ..., b_{k_b}~(n + 1 \le b_i \le n + m) — часть карты Боба.

Вихідні дані

Если такой карты не существует, выведите "No".

В противном случае выведите "Yes" в первой строке, а затем n + m - 1 строк, описывающих возможную карту объектов.

Каждая строка должна содержать два целых числа u_i и v_i — блок охраны и химлаборатория, соединенные i-м туннелем объекта.

Приклад

Код Прюфера для дерева в первом примере имеет вид: (7, 1, 6, 3, 3, 8, 4).

Вхідні дані #1
4 5 4 2
1 3 3 4
7 8
Вихідні дані #1
Yes
1 8
2 7
3 7
4 9
5 1
6 3
7 4
8 3
Вхідні дані #2
4 3 3 1
3 2 2
6
Вихідні дані #2
No
Джерело 2019 ACM NEERC, Полуфинал, Декабрь 1, Задача F