Надійна безпека#9585

Надійна безпека

1 секунда

128 мегабайтів

Легка

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

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

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

Аліса і Боб благополучно повернулися і готові об'єднати свої дані, щоб відновити початкову карту. Вони могли припуститися помилки під час резервного копіювання, що означає, що такої карти не існує. Алісі і Бобу потрібна ваша допомога, щоб відновити будь-яку можливу карту об'єкта, сумісну з їхніми даними, так щоб і частина Аліси, і частина Боба були підпослідовностями коду Прюфера цієї карти.

Вхідні дані

Перший рядок містить чотири цілі числа $n$ , $m$ , $k_{a}$ k_a і $k_{b}$ k_b $(2 \leq n, m \leq 1 0^{5}, 1 \leq k_{a}, k_{b}, k_{a} + k_{b} \leq n + m - 2)$ (2 \le n, m \le 10^5, 1 \le k_a, k_b, k_a + k_b \le n + m - 2).

Другий рядок містить $k_{a}$ k_a цілих чисел $a_{1}, a_{2}, \dots, a_{k_{a}}$ a_1, a_2, \ldots, a_{k_a} $(1 \leq a_{i} \leq n)$ (1 \le a_i \le n) — частина карти Аліси.

Третій рядок містить $k_{b}$ k_b цілих чисел $b_{1}, b_{2}, \dots, b_{k_{b}}$ b_1, b_2, \ldots, b_{k_b} $(n + 1 \leq b_{i} \leq n + m)$ (n + 1 \le b_i \le n + m) — частина карти Боба.

Вихідні дані

Якщо такої карти не існує, виведіть "No".

В іншому випадку виведіть "Yes" у першому рядку, а потім $n + m - 1$ n + m - 1 рядків, які описують можливу карту об'єкта.

Кожен рядок повинен містити два цілі числа $u_{i}$ u_i і $v_{i}$ v_i — підрозділ безпеки і хімічна лабораторія, з'єднані $i$ -м тунелем об'єкта.

Приклади

Код Прюфера для дерева у першому прикладі має вигляд: $(7, 1, 6, 3, 3, 8, 4)$ (7, 1, 6, 3, 3, 8, 4).

Приклад 1

Приклад 2