MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ACM 2016 - Round #1

Ended

A - Salarios

Languages: C, C++, Java, Python, Tiger, JavaScript, Pascal, Haskell, C#
Time & Memory limits: (details)

En la empresa de Fito se están haciendo ajustes al salario de cada empleado. Existen tres categorías de salarios: $1$, $2$ y $3$, siendo la $1$ la más alta y la $3$ la más baja. Cada trabajador tiene un único jefe inmediato (excepto Fito que es el presidente de la empresa), por lo que la jerarquía de mando se puede representar como un árbol con raíz. Se quiere asignar una categoría de salario a cada trabajador, pero esto no es tarea sencilla, pues un jefe se molestará si a alguno de sus empleados directos se le asigna una categoría de salario mejor o igual a la suya. La asignación de salarios deberá entonces minimizar la cantidad de trabajadores que obtienen una categoría de salario mejor o igual que la de su jefe inmediato, teniendo en cuenta que hay algunos trabajadores a los cuales ya se les ha asignado su categoría de salario.

Input

En la primera línea : un entero $N$ $(1 \le N \le 10^6)$, la cantidad de trabajadores en la empresa de Fito.
En las siguientes N líneas : dos enteros $A$ y $B$ $(1 \le A, B \le N)$ en cada línea, indicando que $A$ es jefe inmediato de $B$.
En la próxima línea : un entero $M$ $(0 \le M \le N)$, la cantidad de trabajadores con categoría de salario ya asignada.
En las siguientes M líneas : dos enteros $T$ y $C$ $(1 \le T \le N; 1 \le C \le 3)$ en cada línea, indicando que al trabajador $T$ ya le ha sido asignada la categoría de salario $C$.

Output

En una línea : la cantidad mínima de trabajadores que obtienen una categoría de salario mejor o igual que la de su jefe inmediato.

Sample test(s)

Input
5 1 2 1 4 2 3 2 5 1 3 2
Output
1