Kotlin Heroes: Episode 3 |
---|
Закончено |
Древляндия состоит из $$$n$$$ городов и $$$n-1$$$ двусторонних дорог, соединяющих некоторые пары городов. Из любого города можно добраться до любого другого города. Вы правы — система городов и дорог в Древляндии образует неориентированное дерево.
Правительство объявило тендер на модернизацию инфраструктуры городов, при этом допустимо модернизировать произвольное подмножество $$$S$$$ городов (возможно, все города), которое удовлетворяет следующим требованиям:
Помогите Древляндии с модернизацией — найдите любое из возможных подмножеств $$$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
Название |
---|