After his long journey through the Moldovan landscape, Little IR12660 arrived at one of his last destinations: Ploiești Sud, a city renowned for it's booming petrol industry and coincidentally booming pollution index. As soon as he got here, he realized the city is in dire need of modernization, i.e. dismantling the entire illumination system:

Ploiești Sud can be described as a (connected) tree with $$$N$$$ nodes, each node representing an important landmark. Each landmark comes with it's own streetlight which illuminates it. A lighting plan is a set of streetlights $$$S$$$ which the city administration plans to turn on.

To actually turn them on, they have to pay an electricity company to send electricity to them. However, the electricity company has a trick up their sleeve; they don't have to manually power up all the streetlights in the lighting plan: if there is a streetlight $$$v$$$ currently powered up, and there is a streetlight $$$u$$$ in the lighting plan which is adjacent to $$$v$$$, $$$u$$$ can draw current from $$$v$$$ for free. As such, the electricity company will choose a subset $$$T \subset S$$$ of minimum cardinality such that after manually powering on all the streetlights in $$$T$$$, all other streetlights in $$$S / T$$$ can draw current directly or indirectly from those in $$$T$$$. The cardinality of $$$T$$$ is called the cost of a lighting plan.

Little IR12660 has friends on the city council that told him that the mayor only accepts suggestions for lighting plans whose cost is exactly $$$K$$$. Because Little IR12660 is a big fan of Petrolul Ploiești, he wants to propose a lighting plan that will pass the mayor that is also the most glorious$$$^\ddag$$$, to show that Petrolul is number one.

Ploiești Sud is, however, too big for Little IR12660 to handle, so he asks you to find the most glorious lighting plan in his stead.

$$$^\ddag:$$$ We call a set $$$A$$$ more glorious than $$$B$$$ iff the sequence $$$(a_n)_n$$$, where $$$a_i = 1$$$ iff $$$i \in A$$$ and $$$0$$$ otherwise is smaller lexicographically than sequence $$$(b_n)_n$$$ where $$$b_i = 1$$$ iff $$$i \in B$$$ and $$$0$$$ otherwise. One sequence $$$(x_n)_n$$$ is smaller lexicographically than another sequence $$$(y_n)_n$$$ iff there exists an $$$i$$$ such that for all $$$j \lt i$$$, $$$x_j = y_j$$$, and $$$x_i \lt y_i$$$.