Orden de Ordeño


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

Las N vacas del Granjero Juan (2 \leq N \leq 100), convenientemente numeradas 1...N como siempre, pasan demasiado tiempo en sus cobertizos. Como resultado, han elaborado una compleja estructura social relacionada con el orden en que el Granjero Juan las ordeña cada mañana. Después de semanas de estudio, el Granjero Juan descubrió que esta estructura se basa en dos propiedades clave.

Primero, debido a la jerarquía social de las vacas, algunas vacas insisten en ser ordeñadas antes que otras, según el nivel de estatus social de cada vaca. Por ejemplo, si la vaca 3 tiene el estatus más alto, la vaca 2 tiene un estatus promedio y la vaca 5 tiene un estatus bajo, entonces la vaca 3 tendría que ser ordeñada antes, seguida más tarde por la vaca 2 y finalmente por la vaca 5.

En segundo lugar, algunas vacas solo se permiten ordeñarlas en una posición determinada dentro del pedido. Por ejemplo, la vaca 4 podría insistir en ser ordeñada en segundo lugar entre todas las vacas.

Afortunadamente, el Granjero Juan siempre podrá ordeñar sus vacas en un orden que satisfaga todas estas condiciones.

Desafortunadamente, la vaca 1 se ha enfermado recientemente, por lo que el Granjero Juan quiere ordeñar esta vaca lo antes posible en el orden para que pueda regresar al establo y descansar un poco. Ayude al Granjero Juan a determinar la primera posición en la que puede aparecer la vaca 1 en el orden de ordeño.

Entrada

La primera línea contiene N, M (1 \leq M < N) y K (1 \leq K < N), lo que indica que el Granjero Juan tiene N vacas, M de sus vacas se han ordenado en una jerarquía social y K de sus vacas exigen que se ordeñen en una posición específica en el pedido. La siguiente línea contiene M enteros distintos m_i (1 \leq m_i \leq N). Las vacas presentes en esta línea deben ser ordeñadas en el mismo orden en que aparecen en esta línea. Las siguientes K líneas contienen dos números enteros c_i (1 \leq c_i \leq N) y p_i (1 \leq p_i \leq N), lo que indica que la vaca c_i debe ordeñarse en la posición p_i.

Está garantizado que bajo estas limitaciones, el Granjero Juan podrá construir una orden de ordeño válida.

Salida

Imprima la primera posición que la vaca 1 puede tomar en la orden de ordeño.

Ejemplo de Entrada

6 3 2
4 5 6
5 3
3 1

Ejemplo de Salida

4

Explicación

En este ejemplo, el Granjero Juan tiene seis vacas y la vaca 1 está enferma. Necesita ordeñar la vaca 4 antes que la vaca 5 y la vaca 5 antes que la vaca 6. Además, el Granjero Juan tiene que ordeñar la vaca 3 en la primera posición y la vaca 5 en tercer lugar.

El Granjero Juan tiene que ordeñar la vaca 3 primero, y dado que la vaca 4 tiene que venir antes que la vaca 5, la vaca 4 debe ordeñarse en segundo lugar y la vaca 5 en tercer lugar. Por tanto, la vaca 1 puede ocupar el cuarto lugar como mínimo en el orden.


Comments

There are no comments at the moment.