4. Zimný problém sysľa Mariána

Ako všetci viete, v našich Nízkych Tatrách v hojnom počte žijú sysle. Býva tam aj syseľ Marián. Svoj príbytok si vybudoval tak, že vyhĺbil na lúke priechodný, pohodlný tunel, ktorý na konci rozšíril na priedušnú, útulnú izbu. V nej opäť vyhĺbil niekoľko priechodných, pohodlných tunelov, ktoré na konci rozšíril na priedušné, útulné izby. Takto pokračoval, v každej už vyhĺbenej priedušnej, útulnej izbe vyhĺbil smerom nadol niekoľko (nula alebo viac) priechodných, pohodlných tunelov. Keď skončil, jeho syslie obydlie tvorilo \(n\) útulných, priedušných izieb spojených \(n-1\) priechodnými, pohodlnými tunelmi. Marián bol so svojím výtvorom náramne spokojný.

Jedného večera, zatiaľ čo riešil syslie veci v jednej zo svojich izieb, začalo vonku mrznúť. Mariánovi bolo jasné, že ak by vyliezol do niektorej izby, ktorá je bližšie k povrchu ako tá, v ktorej práve je, tak by určite prechladol. Nič si z toho však nerobil – uložil sa spať v jednej z prístupných izieb (buď ostal v tej, čo bol, alebo sa presunul niekam hlbšie). No nemohol tušiť, že kvôli ukrutnej zime primrzol neďaleký rybník. Žaba Michal sa teda rozhodol, že si nájde priedušnejší, útulnejší príbytok. A tak zamieril priamo do Mariánovej nory. Vďaka priechodnosti a pohodlnosti tunelov bez problémov doskákal až do priedušnej, útulnej izby v ktorej spal Marián. Marián sa v tú noc prebudil na neúprosné chrápanie jeho novonadobudnutého spolubývajúceho.

Čo má teraz robiť? Marián dobre vedel, že ak by Michala vyhnal, tak by v studenej noci určite ochorel. Na to však nemá srdce. Nechal teda žabu spať, prešiel cez priechodný, pohodlný tunel do vedľajšej priedušnej, útulnej izby a horko-ťažko predsa len zaspal. Keď sa ráno zobudil, žaby už nebolo. Marián si však domyslel, že sa táto situácia bude celú zimu opakovať – akonáhle začne večer vonku mrznúť, Marián si bude musieť nájsť takú priedušnú, útulnú izbu, do ktorej sa vie dostať pomocou priechodných, pohodlných tunelov bez toho, aby liezol smerom nahor (tam by totiž prechladol). Hneď na to k nemu doskáče žaba Michal a Mariánovi nedá svojim chrápaním spať. Teraz Marián potrebuje ujsť do inej izby čo najďalej od žaby bez toho aby vyliezol nad izbu v ktorej bol večer (tam sa mu bude najľahšie zaspávať). Marián si ďalšiu noc radšej naplánuje.

Úloha

Izbám v svojej nore priradil Marián čísla od \(1\) po \(n\). Číslo izby, ktorú vyhĺbil ako prvú (teda izby najbližšie k povrchu) označme \(l\). Hĺbka izby je počet tunelov, cez ktoré treba prejsť smerom nadol, aby ste sa do nej dostali z lúky. Hĺbka izby \(l\) je teda 1 a hĺbka každej inej izby je o 1 väčšia než hĺbka izby nad ňou.

Vzdialenosť medzi dvoma izbami je počet tunelov, cez ktoré musíme prejsť, aby sme sa dostali z jednej do druhej.

Mariánova nora môže vyzerať napríklad takto:

Izbu, kde sa Marián zdržiava večer, označme \(v\). Počas celej noci sa Marián nemôže ani na chvíľu ocitnúť v izbe s menšou hĺbkou, než hĺbka izby \(v\). To znamená, že ani počas presunu z izby \(v\) do izby, kam sa prvotne uloží spať, ani počas nočného úteku od žaby nemôže Marián ani len prechádzať cez izbu s menšou hĺbkou ako má izba \(v\). Samozrejme, aj obe izby, kde bude Marián spať, musia byť aspoň tak hlboko ako \(v\).

Marián potrebuje o každej izbe zistiť, aká je dobrá. To znamená, že pre každú izbu ho zaujíma odpoveď na otázku “Ak by som sa večer zdržiaval v tejto izbe a izbu na spanie by som si zvolil čo najlepšie, ako ďaleko od žaby sa mi v noci podarí dostať?” Inými slovami, pre každú izbu \(x\) ho zaujíma najväčšia možná vzdialenosť medzi dvojicou izieb \(y, z\) takou, že z izby \(x\) sa vie dostať do izby \(y\) a z izby \(y\) do izby \(z\) bez toho, aby musel vyliezť do menšej hĺbky než má izba \(x\).

Pomôžte úbohému sysľovi!

Formát vstupu

V prvom riadku sú dve čísla \(n\), \(l\) (\(1 \leq l \leq n \leq 150\,000\)) – počet izieb v Mariánovej nore a číslo izby, ktorá je priamo prepojená s lúkou (a má teda hĺbku \(1\)). Nasleduje \(n-1\) riadkov s dvojicami čísel izieb \(a_i, b_i\), ktoré sú prepojené tunelom. Je zaručené, že z každej izby sa dá postupnosťou tunelov dostať do každej inej práve jedným spôsobom. Izbičky s chodbami teda tvoria strom.

V prvej sade testovacích vstupov navyše platí, že z každej izby ide najviac jeden priechodný, pohodlný tunel do izby s väčšou hĺbkou. To znamená, že nora sa nerozvetvuje, iba stále klesá dodola.

Formát výstupu

Vypíšte \(n\) riadkov. V \(i\)-tom z nich vypíšte hľadanú vzdialenosť pre izbu \(i\), ako je popísané v časti Úloha.

Príklad

Input:

4 2
2 3
4 1
3 4

Output:

0
3
2
1

Toto je príklad vstupu z prvej sady.

Input:

7 3
4 7
2 1
6 2
5 2
3 4
5 3

Output:

0
2
5
1
2
0
0

Toto je syslia nora z obrázku v Úlohe. Ak je Marián večer v niektorej z izieb 1, 6 alebo 7, má smolu a musí v nej ostať po celú noc (teda bude od žaby vzdialený nula). Ak je večer v izbe 2, môže sa uložiť spať do izby 6 a počas noci utiecť do izby 1 (vzdialenosť 2). Ak je večer v izbe 3, môže ísť spať napríklad do izby 1 a v noci sa presunúť do izby 7 (vzdialenosť 5). Ak začína v izbe 4, môže ostať spať v nej a v noci utiecť do izby 7 (vzdialenosť 1). Ak bude večer v izbe 5, môže sa uložiť v izbe 6 a v noci prejsť späť do izby 5 (vzdialenosť 2).