Графічне Божевілля#4138

Графічне Божевілля

3 секунди

256 мегабайтів

Дуже складна

У Байтленді є два провідні виробники відеокарт: Bitotronics та 3D-Bytes. Їхні топові карти дуже схожі. Кожна складається з багатьох вузлів, з'єднаних дротами, які передають оброблюваний сигнал. Продукти містять два типи вузлів: розетки та процесори. Мережа дротів виконує такі умови:

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

Біттю любить експериментувати з комп'ютерним обладнанням. Він придбав дві відеокарти, одну від кожного виробника. Оскільки випадково карти мають однакову кількість розеток, він вирішив підключити кожну розетку карти Bitotronics до окремої розетки карти 3D-Bytes за допомогою кабелів. Пристрій, який він отримав, виглядає так:

Біттю хоче вичавити максимальну обчислювальну потужність з пристрою. Для цього він хоче знайти шлях через дроти та кабелі, яким може пройти оброблюваний сигнал. Шлях повинен відвідати кожен вузол обох карт рівно один раз і починатися та закінчуватися на одному й тому ж вузлі на одній карті. Допоможіть Біттю з'ясувати, чи це можливо.

Вхідні дані

Перша строка вхідних даних містить кількість тестових випадків $T$ . Опис тестових випадків слідує:

Кожен тестовий випадок починається з трьох цілих чисел $k$ , $n$ , $m$ ( $2 \leq k \leq 1000$ 2 \le k \le 1000, $1 \leq n, m \leq 1000$ 1 \le n, m \le 1000), що позначають відповідно кількість розеток на кожній карті, кількість процесорів на карті Bitotronics та кількість процесорів на карті 3D-Bytes. Вузли на картах названі наступним чином:

розетки на карті Bitotronics: AS1, AS2, ..., ASk
процесори на карті Bitotronics: AP1, AP2, ..., APn
розетки на карті 3D-Bytes: BS1, BS2, ..., BSk
процесори на карті 3D-Bytes: BP1, BP2, ..., BPm

Наступні $n + k - 1$ n+k-1 рядків містять опис мережі дротів на карті Bitotronics. Кожен з цих рядків містить назви двох різних вузлів на цій карті, які безпосередньо з'єднані дротом. Опис супроводжується порожнім рядком. Наступні $m + k - 1$ m+k-1 рядків містять опис мережі дротів на карті 3D-Bytes у тому ж форматі. Опис супроводжується ще одним порожнім рядком. Останні $k$ рядків тестового випадку описують кабелі, додані Біттю. Кожен з цих рядків містить назви двох розеток на різних картах, які безпосередньо з'єднані кабелем. Кожна розетка буде присутня рівно в одному з цих $k$ рядків. Після кожного тестового випадку, крім останнього, є порожній рядок.

Вихідні дані

Надрукуйте відповіді на тестові випадки в порядку їх появи у вхідних даних. Для кожного тестового випадку надрукуйте один рядок, що містить відповідь. Якщо не існує шляху з бажаними властивостями, виведіть NO. Інакше виведіть YES, за яким слідує опис шляху: $n + m + 2 k$ n+m+2k різних вузлів у порядку, в якому сигнал буде проходити через них. Кожні два послідовні вузли повинні бути з'єднані дротом або кабелем. Крім того, перший і останній вузол повинні бути з'єднані.

Приклади

Приклад 1