Kaaleppi-serkku etsii myös uutta asuntoa. Yksi tärkeä tekijä kaupungin valinnassa on, että siitä pääsee sujuvasti muihin kaupunkeihin. Tarkemmin sanoen Kaaleppi on kiinnostunut siitä, mikä on yhteismatka kaikkiin muihin kaupunkeihin.

Kaikki kaupungit ovat yhteydessä toisiinsa, ja teitä on tarkalleen yksi vähemmän kuin kaupunkeja. Voisitko auttaa Kaaleppia laskemaan jokaiselle kaupungille, mikä on yhteismatka kaupungista muihin kaupunkeihin?

Syöte

Ensimmäisellä rivillä on kokonaisluku n, kaupunkien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n.

Tämän jälkeen syötteessä on n-1 riviä, joista jokainen kuvaa yhden tien. Rivillä on kaksi kokonaislukua a ja b: mistä kaupungista tie alkaa ja mihin se päättyy.

Tuloste

Ohjelmasi tulee tulostaa jokaiselle kaupungille 1,2,\ldots,n yhteismatka kaikkiin muihin kaupunkeihin.

Rajat

• 2 \leq n \leq 5\cdot 10^4

Esimerkki

Syöte:

4
1 2
2 3
2 4

Tuloste:

5
3
5
5

Selitys: Kaupungista 1 matkat kaupunkeihin 2, 3 ja 4 ovat 1, 2 ja 2. Yhteismatka on näiden summa eli 5.