Forças Armadas
As forças armadas de um certo país são compostas de $$n$$ membros, e tem um a hierarquia em que cada membro tem exatamente um superior. O rank do presidente é 1 e o rank de cada membro é o rank do seu superior mais 1.
Seu objetivo é descobrir quem é o presidente e para isso você fará um relatoŕio. Esse relatório consiste em achar para cada membro das forças armadas, quantos ranks distintos haveriam caso ele fosse o presidente, assumindo hierarquias válidas para cada caso.
Entrada
A primeira linha contém um inteiro $$n\ (1 \leq n \leq 500000)$$ – o numero de membros nas forçar armadas.
As próximas $$n-1$$ linhas contém relações de superioridade, da forma $$u\ v$$ conde isso indica que ou $$u$$ é o superior de $$v$$ ou $$v$$ é o superior de $$u$$, depedenedo de quem é o presidente.
Saída
Você deve imprimir $$n$$ linhas. Na linha $$i$$ você deve imprimir um intero $$x$$ – o número de ranks distintos caso $$i$$ fosse presidente.
Exemplos
| Entrada | Saída |
| 3
2 1 2 3 |
3
2 3 |
Explicação
- Caso 1 seja presidente:
- Caso 2 seja presidente:
- Caso 3 seja presidente: