E. Модернизация в Древляндии
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Древляндия состоит из $$$n$$$ городов и $$$n-1$$$ двусторонних дорог, соединяющих некоторые пары городов. Из любого города можно добраться до любого другого города. Вы правы — система городов и дорог в Древляндии образует неориентированное дерево.

Правительство объявило тендер на модернизацию инфраструктуры городов, при этом допустимо модернизировать произвольное подмножество $$$S$$$ городов (возможно, все города), которое удовлетворяет следующим требованиям:

  • подмножество городов должно быть «связным», то есть из любого города подмножества $$$S$$$ можно доехать до любого другого города подмножества $$$S$$$ по дорогам, перемещаясь только по городам из $$$S$$$;
  • количество «тупиковых» городов в $$$S$$$ должно быть равно заданному числу $$$k$$$. Город является тупиковым, если он является единственным городом в $$$S$$$, либо связан ровно с одним другим городом из $$$S$$$.
Здесь изображён один из возможных способов выбрать $$$S$$$ (синие вершины) для заданной конфигурации и $$$k=4$$$. Тупиковыми вершинами являются вершины с номерами $$$1$$$, $$$4$$$, $$$6$$$ и $$$7$$$.

Помогите Древляндии с модернизацией — найдите любое из возможных подмножеств $$$S$$$ или определите, что такого подмножества не существует.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют сами наборы входных данных.

Каждый набор входных данных начинается строкой, которая содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le n$$$) — количество городов в Древляндии и количество «тупиковых» городов в подмножестве $$$S$$$.

Далее следует $$$n-1$$$ строка с описаниями дорог. Каждая дорога задаётся двумя целыми числами $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — номерами городов, которые соединены дорогой. Гарантируется, что из каждого города можно добраться до любого другого, перемещаясь только вдоль дорог.

Сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите Yes или No (в любом регистре), в зависимости от того, существует ответ или нет. Если ответ существует, то далее выведите $$$m$$$ ($$$1 \le m \le n$$$) — количество городов в найденном подмножестве. Затем выведите $$$m$$$ различных чисел от $$$1$$$ до $$$n$$$ — номера городов, которые составляют найденное подмножество. Номера городов можно выводить в любом порядке. Если решений несколько, то выведите любое из них.

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