Графічне Божевілля
У Байтленді є два провідні виробники відеокарт: Bitotronics та 3D-Bytes. Їхні топові карти дуже схожі. Кожна складається з багатьох вузлів, з'єднаних дротами, які передають оброблюваний сигнал. Продукти містять два типи вузлів: розетки та процесори. Мережа дротів виконує такі умови:
Кожна розетка підключена рівно до одного процесора і не підключена до інших розеток.
Кожен процесор підключений щонайменше до двох інших вузлів.
Для будь-яких двох вузлів у мережі існує рівно один шлях дротів, що їх з'єднує. Іншими словами, граф з'єднань між вузлами є деревом.
Біттю любить експериментувати з комп'ютерним обладнанням. Він придбав дві відеокарти, одну від кожного виробника. Оскільки випадково карти мають однакову кількість розеток, він вирішив підключити кожну розетку карти Bitotronics до окремої розетки карти 3D-Bytes за допомогою кабелів. Пристрій, який він отримав, виглядає так:
Біттю хоче вичавити максимальну обчислювальну потужність з пристрою. Для цього він хоче знайти шлях через дроти та кабелі, яким може пройти оброблюваний сигнал. Шлях повинен відвідати кожен вузол обох карт рівно один раз і починатися та закінчуватися на одному й тому ж вузлі на одній карті. Допоможіть Біттю з'ясувати, чи це можливо.
Вхідні дані
Перша строка вхідних даних містить кількість тестових випадків T. Опис тестових випадків слідує:
Кожен тестовий випадок починається з трьох цілих чисел k, n, m (2 ≤ k ≤ 1000, 1 ≤ n, m ≤ 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 рядків містять опис мережі дротів на карті Bitotronics. Кожен з цих рядків містить назви двох різних вузлів на цій карті, які безпосередньо з'єднані дротом. Опис супроводжується порожнім рядком. Наступні m+ k−1 рядків містять опис мережі дротів на карті 3D-Bytes у тому ж форматі. Опис супроводжується ще одним порожнім рядком. Останні k рядків тестового випадку описують кабелі, додані Біттю. Кожен з цих рядків містить назви двох розеток на різних картах, які безпосередньо з'єднані кабелем. Кожна розетка буде присутня рівно в одному з цих k рядків. Після кожного тестового випадку, крім останнього, є порожній рядок.
Вихідні дані
Надрукуйте відповіді на тестові випадки в порядку їх появи у вхідних даних. Для кожного тестового випадку надрукуйте один рядок, що містить відповідь. Якщо не існує шляху з бажаними властивостями, виведіть NO. Інакше виведіть YES, за яким слідує опис шляху: n+m+2k різних вузлів у порядку, в якому сигнал буде проходити через них. Кожні два послідовні вузли повинні бути з'єднані дротом або кабелем. Крім того, перший і останній вузол повинні бути з'єднані.