README.md

Task 1. Подаръци 1 (Medium)

HackerRank link

Statement:

Вие сте изпълнителен директор на технологичния гигант Амазонка. Тъй като наближават коледните празници, се налага да купите подаръци на всички свои подчинени, било то преки или косвени (подчинени на подчинени)... така, че да няма много причини да мрънкат. Проблемът е обаче, че ако вие подарите на даден служител подарък, а прекият му началник не му подари, то служителят ще мрънка на прекия си началник... абе няма угодия с тия хора.

Вашата задача е по дадена йерархичната структура на компанията да прецените кой началник колко подаръка ще купи, ако знаете че всеки началник ще купи подарък на всичките си служители.

Йерархичната структура в компанията е под формата на дърво, индексирано от $0$ до $N$, като вие с сте в корена с индекс $0$ и всеки връх съответства на даден човек от компанията. Ако връх с индекс $x$ е родител на друг връх с индекс $y$, това значи, че човекът, съответстващ на върха с индекс $x$, e пряк началник на човека, съответстващ на индекс $y$.

Input Format

Въвежда ви се броя $N$ на служителите. След това на всеки ред се въвеждат по две числа $x$ и $y$, като това значи, че човекът, чийто връх в дървото е с индекс $x$, е родител на човека с индекс в дървото $y$.

Constraints

$1\le N\le10^6$

Output Format

Извеждат се $N$ числа, разделени с празно място, като $i$-тото число отговаря на броя подаръци, които трябва да купи човекът, който отговаря на върха с индекс $i$ в дървото.

Sample Input 0

9
0 1
0 2
1 3
1 4
1 5
1 6
4 7
7 8

Sample Output 0

8 6 0 0 2 0 0 1 0