F3. Древо жизни (сложная)
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для увеличения олимпиадности задачи зомби забрали все рисунки кроме двух! Помогите Хайди восстановить описание Древа жизни только по двум имеющимся рисункам.

Входные данные

Формат входных данных соответствует средней версии данной задачи, с тем исключением, что ограничение на n есть 2 ≤ n ≤ 1000 и k = 2.

Выходные данные

Совпадает со средней версией данной задачи.

Пример
Входные данные
1
9 2
6
4 3
5 4
6 1
8 6
8 2
7 1
5
8 6
8 7
8 1
7 3
5 1
Выходные данные
YES
2 1
3 1
5 4
6 5
7 6
8 5
9 8
1 4