Milking Order (Bronze)#10382
Le mucche di Farmer John, numerate comodamente come sempre, si ritrovano ad avere troppo tempo libero sui loro zoccoli. Di conseguenza, hanno elaborato una complessa struttura sociale legata all'ordine in cui Farmer John le munge ogni mattina. Dopo settimane di studio, Farmer John ha scoperto che questa struttura si basa su due proprietà fondamentali.
Prima di tutto, a causa della gerarchia sociale delle mucche, alcune mucche insistono per essere munte prima di altre mucche, a seconda del loro stato sociale. Ad esempio, se la mucca ha lo stato sociale più alto, la mucca ha uno stato medio e la mucca ha uno stato basso, allora la mucca deve essere munta prima della mucca , e la mucca prima della mucca .
In secondo luogo, alcune mucche si lasciano mungere solo in una determinata posizione nell'ordine. Ad esempio, la mucca potrebbe insistere per essere munta per seconda.
Fortunatamente, Farmer John può sempre mungere le sue mucche in un ordine che soddisfi tutte queste condizioni.
Sfortunatamente, la mucca si è recentemente ammalata, quindi Farmer John vuole mungerla il prima possibile, in modo che possa tornare nella stalla e riposarsi un po', di cui ha tanto bisogno. Aiuta Farmer John a determinare la posizione più anticipata che la mucca può occupare nell'ordine di mungitura.
La prima riga contiene tre interi , e k~(2 \le n \le 100, 1 \le m < n, 1 \le k < n): Farmer John ha mucche, di esse formano una gerarchia sociale, e di esse pretendono di essere munte in posizioni specifiche nell'ordine. La seconda riga contiene interi distinti m_i~(1 \le m_i \le n); le mucche elencate in questa riga devono essere munte nello stesso ordine in cui appaiono. Ciascuna delle successive righe contiene due interi c_i e p_i~(1 \le c_i, p_i \le n), il che significa che la mucca c_i deve essere munta nella posizione p_i.
È garantito che esista un ordine di mungitura valido sotto questi vincoli.
Stampa un intero — la posizione più anticipata che la mucca può occupare nell'ordine di mungitura.
Esempio 1
In questo esempio, Farmer John ha mucche, e la mucca è malata. Deve mungere la mucca prima della mucca , e la mucca prima della mucca . Inoltre, la mucca deve essere munta per prima, e la mucca per terza.
Poiché la mucca viene munta per prima e la mucca deve venire prima della mucca , che viene munta per terza, la mucca deve essere munta per seconda. Quindi, la posizione più anticipata per la mucca è la quarta.