Соціальне дистанціювання
Ось що можна сказати про студентів: вони не люблять робити зайву роботу і прагнуть триматися на відстані від інших. Перше, ймовірно, пояснює, чому їхній відділ має структуру дерева (будівництво коридору між двома вже опосередковано з'єднаними кімнатами було б марною тратою часу); саме тому вони почуваються комфортно під час триваючої пандемії. Тепер соціальне дистанціювання - це не розкіш, а норма!
Однак, будівлі у формі дерева та дистанціювання від інших не завжди є хорошою ідеєю. Зараз у деяких кімнатах проживає k студентів, і через політику дистанціювання в кожній кімнаті може бути не більше одного студента. Крім того, жодні два студенти не можуть перебувати в кімнатах, безпосередньо з'єднаних коридором.
Скоро розпочнеться конкурс ICPC, і студенти поспішають зайняти місця за комп'ютерами, розташованими по всьому відділу. У деяких кімнатах є k комп'ютерів - стільки ж, скільки студентів; крім того, щоб забезпечити дистанціювання, жодні два комп'ютери не повинні бути в одній кімнаті, і жодні дві кімнати, безпосередньо з'єднані одна з одною, не повинні містити комп'ютери. Студенти можуть вільно обирати комп'ютери, але вони повинні постійно дотримуватися соціального дистанціювання, тому переміщення їх у потрібні кімнати може бути складним, якщо не неможливим.
Ви - безжалісний організатор ICPC і творець неймовірного набору задач. Спостерігаючи, як студенти метушаться, ви усвідомлюєте жахливу істину: якщо студенти не встигнуть дістатися до своїх кімнат вчасно, вони не зможуть взяти участь у змаганні, а значить, вся ваша кропітка робота з підготовки нерозв'язних задач піде нанівець! Звісно, ви не можете цього допустити.
Враховуючи поточне розташування студентів і комп'ютерів, спроектуйте послідовність дій, яка переміщує кожного студента в кімнату з комп'ютером. Кожна така дія повинна переміщати студента в сусідню кімнату; після кожної дії жодні два студенти не повинні перебувати в одній кімнаті або в двох сусідніх кімнатах. Залишок часу до початку змагання дозволяє вам виконати не більше 4 * n^2 ходів, де n - кількість кімнат. Цілком можливо, що ваша задача невиконувана, але є тільки один спосіб це з'ясувати...
Вхідні дані
Перша рядок містить кількість тестів z (1 ≤ z ≤ 10^5). Далі йдуть описи тестів.
Перша рядок кожного тесту містить одне ціле число n (2 ≤ n ≤ 2000) - кількість кімнат у будівлі.
Кожна з наступних n - 1 рядків містить два цілі числа u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n) - дві кімнати, з'єднані коридором. Гарантується, що описані коридори утворюють дерево (зв'язний граф без циклів).
У наступній рядку записано одне ціле число k (1 ≤ k < n) - кількість студентів (і комп'ютерів).
Наступна рядок містить цілі числа s[1], ..., s[k] (1 ≤ s[1] < s[2] < ... < s[k] ≤ n) - початкові місця розташування студентів.
Наступна рядок містить цілі числа c[1], ..., c[k] в аналогічному форматі, що позначають кімнати з комп'ютерами.
Гарантується, що хоча б один студент знаходиться в кімнаті без комп'ютера.
Сума n^2 по всіх тестах не перевищує 4 * 10^7.
Вихідні дані
Для кожного тесту виведіть "YES", якщо можливо перевести студентів у кімнати з комп'ютерами з дотриманням соціальної дистанції, і "NO" інакше. У першому випадку в наступних рядках виведіть будь-яке допустиме рішення. Опис рішення повинно починатися з одного цілого числа m (1 ≤ m ≤ 4 * n^2), що позначає кількість ходів. Далі повинно слідувати m рядків, кожна з яких описує один хід з двома цілими числами a[i], b[i] (1 ≤ a[i] ≠ b[i] ≤ n), що означає, що студент, який в даний момент знаходиться в кімнаті a[i], повинен переїхати в кімнату b[i], яка з'єднана з a[i] коридором.
Вам не потрібно мінімізувати довжину рішення.