Natal do Flúcio
Flúcio gosta muito de árvores. Como o Natal está chegando ele decide procurar por diferentes tipos de árvores iluminadas para decorar sua casa. Durante a busca, ele descobre as árvores de propagação. Essas árvores possuem uma propriedade especial, elas conseguem mudar a frequência dos pisca-pisca (famosas lâmpadas natalinas) que ficam em seus nós e propagar essa alteração para outros pisca-pisca da árvore.
Depois de muito tempo observando as árvores de propagação Flúcio concluiu que quando uma das lâmpadas recebe uma corrente diferente de energia a mesma sofre uma alteração em sua frequência de piscadas ela altera propaga piscadas para as lâmpadas que estão diretamente ligadas a ela, e estas propagam para as lâmpadas que estão diretamente ligadas a ela (suas "filhas"), e assim sucessivamente até chegar em uma lâmpada que não possui outras ligações.
Sabendo disso, Flúcio compra uma árvore de propagação e resolve testá-la em casa. Para isso anota a sequência desses testes em seu caderno, que consistem em:
- provoca uma alteração x na frequência de piscadas da lâmpada do nó u.
- consulta a frequência de piscadas da lâmpada do nó u.
Vale lembrar que Flúcio faz anotações em seu caderno e que a árvore possui lâmpadas ( nós) e que a lâmpada é a raíz da ávore.
Entrada
A entrada é composta por dois inteiros e . A segunda linha contém n inteiros . Cada uma das próximas contém dois inteiros e representando uma ligação entre as lâmpadas e . Cada uma das próximas contém um teste feito por Flúcio no formato descrito anteriormente. E garantido para todas as anotações que: e .
Saída
Para cada um dos testes tipo você deve imprimir a resposta. Os testes devem ser respondidos na ordem que foram apresentados na entrada.
Exemplos
Entrada |
Saída |
5 5 1 2 1 1 2 1 2 1 3* 2 4 2 5 1 2 3 1 1 2 2 1 2 2 2 4 |
3 3 0 |