Соціальне дистанціювання#11106
Ось що можна сказати про студентів: вони не люблять робити зайву роботу і прагнуть триматися на відстані від інших. Перше, ймовірно, пояснює, чому їхній відділ має структуру дерева (будівництво коридору між двома вже опосередковано з'єднаними кімнатами було б марною тратою часу); саме тому вони почуваються комфортно під час триваючої пандемії. Тепер соціальне дистанціювання - це не розкіш, а норма!
Однак, будівлі у формі дерева та дистанціювання від інших не завжди є хорошою ідеєю. Зараз у деяких кімнатах проживає студентів, і через політику дистанціювання в кожній кімнаті може бути не більше одного студента. Крім того, жодні два студенти не можуть перебувати в кімнатах, безпосередньо з'єднаних коридором.
Скоро розпочнеться конкурс ICPC, і студенти поспішають зайняти місця за комп'ютерами, розташованими по всьому відділу. У деяких кімнатах є комп'ютерів - стільки ж, скільки студентів; крім того, щоб забезпечити дистанціювання, жодні два комп'ютери не повинні бути в одній кімнаті, і жодні дві кімнати, безпосередньо з'єднані одна з одною, не повинні містити комп'ютери. Студенти можуть вільно обирати комп'ютери, але вони повинні постійно дотримуватися соціального дистанціювання, тому переміщення їх у потрібні кімнати може бути складним, якщо не неможливим.
Ви - безжалісний організатор ICPC і творець неймовірного набору задач. Спостерігаючи, як студенти метушаться, ви усвідомлюєте жахливу істину: якщо студенти не встигнуть дістатися до своїх кімнат вчасно, вони не зможуть взяти участь у змаганні, а значить, вся ваша кропітка робота з підготовки нерозв'язних задач піде нанівець! Звісно, ви не можете цього допустити.
Враховуючи поточне розташування студентів і комп'ютерів, спроектуйте послідовність дій, яка переміщує кожного студента в кімнату з комп'ютером. Кожна така дія повинна переміщати студента в сусідню кімнату; після кожної дії жодні два студенти не повинні перебувати в одній кімнаті або в двох сусідніх кімнатах. Залишок часу до початку змагання дозволяє вам виконати не більше 4 \cdot n^2 ходів, де - кількість кімнат. Цілком можливо, що ваша задача невиконувана, але є тільки один спосіб це з'ясувати...
Перший рядок містить кількість тестів (1 \le z \le 10^5). Далі йдуть описи тестів.
Перший рядок кожного тесту містить одне ціле число (2 \le n \le 2000) - кількість кімнат у будівлі.
Кожна з наступних n - 1 рядків містить два цілі числа u_i, v_i (1 \le u_i \ne v_i \le n) - дві кімнати, з'єднані коридором. Гарантується, що описані коридори утворюють дерево (зв'язний граф без циклів).
У наступному рядку записано одне ціле число (1 \le k < n) - кількість студентів (і комп'ютерів).
Наступний рядок містить цілі числа s_1, ..., s_k (1 \le s_1 < s_2 < ... < s_k \le n) - початкові місця розташування студентів.
Наступний рядок містить цілі числа c_1, ..., c_k в аналогічному форматі, що позначають кімнати з комп'ютерами.
Гарантується, що хоча б один студент знаходиться в кімнаті без комп'ютера.
Сума n^2 по всіх тестах не перевищує 4 \cdot 10^7.
Для кожного тесту виведіть "YES", якщо можливо перевести студентів у кімнати з комп'ютерами з дотриманням соціальної дистанції, і "NO" інакше. У першому випадку в наступних рядках виведіть будь-яке допустиме рішення. Опис рішення повинно починатися з одного цілого числа (1 \le m \le 4 \cdot n^2), що позначає кількість ходів. Далі повинно слідувати рядків, кожна з яких описує один хід з двома цілими числами a_i, b_i (1 \le a_i \ne b_i \le n), що означає, що студент, який в даний момент знаходиться в кімнаті a_i, повинен переїхати в кімнату b_i, яка з'єднана з a_i коридором.
Вам не потрібно мінімізувати довжину рішення.
Приклад 1