|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
ACM 2016 - Round #1Ended |
A - Salarios
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, 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