Nagomi, care a ajuns la o înțelegere cu proprietara hotelului, află că paturile sunt echipate cu ace otrăvite care pot înțepa persoana care doarme fără să o trezească. Ea dobândește un dispozitiv special care are următoarea abilitate: pentru 2 camere $a$ și $b$, activează acele camerelor de pe lanțul dintre $a$ și $b$. Procesul de înțepare efectuat simultan pe toate camerele durează o secundă.

Nagomi stabilește niște activări, poate cu antipatie pe anumite alte servitoare. Se mai știe un lucru: membrii unei cafenele sunt atât de conectați între ei, încât înțeparea unuia îi afectează pe toți. Fiecare cafenea are toleranța ei, adică numărul maxim de înțepături pe care poate să îl suporte fără să fie distrus. Acum Nagomi se întreabă: pentru fiecare clan, care este momentul de timp în care acesta este distrus ?

Nagomi stabilește niște activări, poate cu antipatie pe anumite alte servitoare. Se mai știe un lucru: membrii unei cafenele sunt atât de conectați între ei, încât înțeparea unuia îi afectează pe toți. Fiecare cafenea are toleranța ei, adică numărul maxim de înțepături pe care poate să îl suporte fără să fie distrus. Acum Nagomi se întreabă: pentru fiecare clan, care este momentul de timp în care acesta este distrus?

Sever, mândru de faptul că a mai consumat o rezervă de marker, așteaptă răbdător un răspuns riguros.
h2. Date de intrare

Pe prima linie a fişierului de intrare  se afla numerele N si M

Pe prima linie a fişierului de intrare $sever.in$ se afla numerele $N$ și $M$, reprezentând numărul de camere, respectiv numărul de clanuri. Camerele sunt numerotate de la $1$ la $N$. Pe următoarele $N-1$ linii se află câte $2$ numere, $x$ și $y$, cu semnificația că există conexiune între camera $x$ și camera $y$.

h2. Date de ieşire