Empresa

Devido ao seu sucesso na primeira fase da OBI, a pequena empresa IOI (Insatisfação Observada International) te ofereceu uma entrevista de estágio. Como parte do processo seletivo, você deve ajudar a empresa a avaliar a satisfação dos funcionários com seus empregos.

Na hierarquia da organização, cada funcionário (exceto o fundador) possui um chefe. A empresa valoriza experiência no trabalho: o chefe de todo funcionário entrou na empresa antes dele. Para cada funcionário, os seus subordinados diretos são os funcionários que têm ele como chefe.

Cada funcionário possui um salário mensal, e um estudo feito pela empresa revelou que existe um jeito simples de descobrir quais funcionários estão insatisfeitos: um funcionário está insatisfeito se, e somente se, algum dos seus subordinados diretos ganha mais do que ele (note que ele está satisfeito se seus subordinados ganham tanto quanto ele).

Com o fim do trimestre chegando, o time de Recursos Humanos está considerando ajustar os salários de alguns funcionários, possivelmente aumentando ou reduzindo o valor mensal (porém, para evitar confusão, eles podem alterar o salário de cada funcionário no máximo uma vez). Mas, primeiro, eles precisam avaliar a insatisfação geral dos funcionários durante essa série de ajustes.

Sua tarefa é, dada a estrutura hierárquica da empresa, os salários iniciais, e a sequência considerada de ajustes, determinar o número total de funcionários insatisfeitos inicialmente e após cada ajuste.

Entrada

A primeira linha de entrada contém um inteiro $N$, indicando o número de funcionários da empresa. Os funcionários são identificados de $1$ a $N$ de acordo com a ordem em que entraram na organização. O fundador é identificado pelo número $1$.

Cada uma das $N$ linhas seguintes descreve um funcionário: a linha $i + 1$ contém dois inteiros, $C_i$ e $S_i$, indicando o chefe e o salário do funcionário $i$, respectivamente. É garantido que $C_1 = 1$ (consideramos que o fundador é chefe de si mesmo) e que $C_i < i$ para todos os outros funcionários (ou seja, o chefe de um funcionário entrou antes dele).

A próxima linha contém um inteiro $A$, indicando o número de ajustes de salários a serem feitos. Finalmente, as próximas $A$ linhas contêm a sequência de ajustes: cada linha contém dois inteiros, $I$ e $X$, indicando que o salário mensal do funcionário $I$ foi alterado para $X$. É garantido que nenhum funcionário tem o salário alterado mais do que uma vez. Observe que os ajustes são cumulativos (não desfazemos o ajuste $i - 1$ antes de fazer o ajuste $i$).

Saída

Seu programa deve produzir $A + 1$ linhas, cada uma contendo um único inteiro. A primeira linha deve conter o número de funcionários insatisfeitos antes dos ajustes. As próximas $A$ linhas devem conter os números de funcionários insatisfeitos após cada ajuste.

Restrições

• $1 \leq N \leq 2\ 000$
• $0 \leq A \leq N$
• $C_1 = 1$ e $1\leq C_i < i$ para $i > 1$
• $1\leq S_i\leq 1\ 000\ 000$
• $1 \leq I \leq N$
• $1\leq X\leq 1\ 000\ 000$
• Os valores de $I$ são todos distintos entre si (ou seja, cada funcionário tem o salário ajustado no máximo uma vez).

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (40 pontos): $N \leq 100$ e $A = 0$ – ou seja, nenhum ajuste será feito, e você só precisa calcular a insatisfação total inicial. (Veja o exemplo de entrada 1).
• Subtarefa 2 (30 pontos): $N \leq 100$.
• Subtarefa 3 (30 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

7
1 300
1 350
1 200
3 150
3 250
2 350
3 100
0

Exemplo de saída 1

2

Explicação do exemplo 1: Veja a figura abaixo. Os funcionários insatisfeitos são o $1$ (pois seu subordinado direto $2$ tem um salário maior) e o $3$ (pois seu subordinado direto $5$ tem um salário maior). Note que o funcionário $2$ não está insatisfeito de seu subordinado direto $6$ ganhar exatamente o mesmo que ele.

Exemplo de entrada 2

5
1 500
1 400
2 300
3 450
4 300
2
4 300
3 500

Exemplo de saída 2

1
0
1

Explicação do exemplo 2: Inicialmente (figura a), apenas o funcionário $3$ está insatisfeito. Observe que, apesar do funcionário $4$ ter um salário maior que o funcionário $2$, o funcionário $2$ não está insatisfeito pois o $4$ não é um subordinado direto do $2$. Após o primeiro ajuste (figura b), o salário do funcionário $4$ cai, deixando o funcionário $3$ satisfeito. Após o segundo ajuste (figura c), o salário do funcionário $3$ sobe, tornando o funcionário $2$ insatisfeito.

Exemplo de entrada 3

6
1 100
1 200
1 300
2 400
3 500
3 600
3
1 500
3 550
4 200

Exemplo de saída 3

3
2
3
2