Pacman má pred sebou novú výzvu: level so stromovou topológiou. V leveli je rozmiestnených $n$ značiek. Na každej značke je na začiatku položená jedna chutná gulička. Niektoré dvojice značiek sú prepojené chodbami. Chodieb je presne $n-1$ a sú navrhnuté tak, aby sa pacman vedel dostať od každej značky ku každej inej. Prejsť ľubovoľnou chodbou trvá presne jednu sekundu.
Level má časový limit $t$ sekúnd. Hra začína tým, že si hráč zvolí značku, kde chce začínať. Umiestni tam pacmana, ten zožerie príslušnú guličku a začína bežať čas. Hráč sa následne môže nanajvýš $t$-krát pohnúť na susednú značku. Zakaždým, keď pacman navštívi značku s guličkou, okamžite ju zožerie. (Každú guličku samozrejme môže zožrať len raz.)
Nájdite optimálny spôsob ako hrať daný level: postupnosť ťahov, pri ktorej pacman stihne vyžrať najviac guličiek. Ak existuje viacero možností s rovnakým počtom zjedených guličiek, lepšia je rýchlejšia.
V prvom riadku vstupu je počet značiek $n$ a časový limit $t$. Môžete predpokladať, že $2\leq n\leq 500\,000$ a $1\leq t\leq 200\,000\,000$. Značky majú pridelené poradové čísla od 1 do $n$.
Nasleduje $n-1$ riadkov popisujúcich jednotlivé chodby. Každý z týchto riadkov obsahuje čísla dvoch značiek, ktoré sú spojené priamou chodbou.
V prvom riadku výstupu vypíšte najväčší počet guličiek, ktoré vie pacman v časovom limite zožrať.
V druhom riadku vypíšte najmenší čas $s$, za ktorý to vie dosiahnuť.
V treťom riadku vypíšte postupnosť $s+1$ čísel: najskôr číslo značky, kde má pacman začať, a následne $s$ čísel značiek, ktoré má postupne navštíviť.
Vždy existuje viac možností, čo vypísať v treťom riadku. Môžete si vybrať ľubovoľnú z nich.
7 6
1 2
2 3
2 5
5 6
5 7
4 5
5
5
4 5 7 5 2 1
Máme 7 značiek a 6 sekúnd. Tvar levelu ale určuje, že stíhame zjesť nanajvýš 5 guličiek. Ak ale chceme zjesť 5 guličiek, netreba nám na to 6 sekúnd, dá sa to aj za 5.