Котомережа
Обмеження: 2 сек., 256 МіБ
Зеник та Марічка побудували неймовірну систему коробок та тунелів для їхніх \(k\) котів (\(k\) — парне число). Усього в мережі є \(n\) коробок, які зв’язані \(n-1\) двосторонніми тунелями так, що існує шлях між будь-якою парою коробок. Іншими словами, мережа представлена деревом з \(n\) вершин, пронумерованих цілими числами від 1 до \(n\) включно.
Відомо, що \(i\)-й кіт базується в коробці з номером \(p_i\). Немає коробки, у якій базується більше за одного кота. Зеник та Марічка хочуть поділити котів на пари таким чином, щоб не існувало двох таких пар, які мають спільну вершину на шляхах між базами.
Ваше завдання — знайти можливе розбиття на пари.
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(k\) — кількість коробок та котиків.
У другому рядку задано \(k\) цілих чисел, розділених пробілами — бази котиків \(p_i\).
У наступних \(n-1\) рядках описуються тунелі у вигляді пар індексів коробок, які з’єднує відповідний тунель.
Вихідні дані
Якщо отримати потрібне розбиття неможливо, виведіть
NO
.
Інакше в першому рядку виведіть YES
.
У наступних \(\frac{k}{2}\) рядках виведіть розбиття на пари, по одній парі на рядок — індекси відповідних коробок у парі.
Якщо існує декілька варіантів розбиття на пари, дозволяється вивести будь-який із них.
Обмеження
\(2 \le k \le n \le 10^5\),
\(k\) — парне число.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 2 3 4 1 2 2 3 2 4 | NO |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 4 5 4 1 3 1 2 2 5 2 3 3 4 | YES 1 5 3 4 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|