Orden de Ordeño (Bronce)#10382
Las vacas de Farmer John, numeradas convenientemente como siempre, tienen demasiado tiempo libre en sus pezuñas. Como resultado, han elaborado una compleja estructura social relacionada con el orden en el que Farmer John las ordeña cada mañana. Después de semanas de estudio, Farmer John ha descubierto 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 vacas, dependiendo de su estatus social. Por ejemplo, si la vaca tiene el estatus más alto, la vaca tiene un estatus promedio y la vaca tiene un estatus bajo, entonces la vaca debe ser ordeñada antes que la vaca , y la vaca antes que la vaca .
Segundo, algunas vacas solo se dejan ordeñar en una posición determinada del orden. Por ejemplo, la vaca podría insistir en ser ordeñada en segundo lugar.
Afortunadamente, Farmer John siempre puede ordeñar a sus vacas en un orden que satisfaga todas estas condiciones.
Desafortunadamente, la vaca se ha enfermado recientemente, por lo que Farmer John quiere ordeñarla lo antes posible, para que pueda regresar al establo y descansar lo que tanto necesita. Ayuda a Farmer John a determinar la posición más temprana que la vaca puede ocupar en el orden de ordeño.
La primera línea contiene tres enteros , y k~(2 \le n \le 100, 1 \le m < n, 1 \le k < n): Farmer John tiene vacas, de ellas forman una jerarquía social, y de ellas exigen ser ordeñadas en posiciones específicas del orden. La segunda línea contiene enteros distintos m_i~(1 \le m_i \le n); las vacas listadas en esta línea deben ser ordeñadas en el mismo orden en el que aparecen. Cada una de las siguientes líneas contiene dos enteros c_i y p_i~(1 \le c_i, p_i \le n), lo que significa que la vaca c_i debe ser ordeñada en la posición p_i.
Se garantiza que existe un orden de ordeño válido bajo estas restricciones.
Imprime un entero — la posición más temprana que la vaca puede ocupar en el orden de ordeño.
Ejemplo 1
En este ejemplo, Farmer John tiene vacas, y la vaca está enferma. Debe ordeñar a la vaca antes que a la vaca , y a la vaca antes que a la vaca . Además, la vaca debe ser ordeñada primero, y la vaca en tercer lugar.
Como la vaca es ordeñada primero y la vaca debe venir antes que la vaca , que es ordeñada en tercer lugar, la vaca debe ser ordeñada en segundo lugar. Por lo tanto, la posición más temprana para la vaca es la cuarta.