Sağım Sırası (Bronz)#10382

Sağım Sırası (Bronz)

1 saniye

128 megabayt

Orta

Farmer John'un her zamanki gibi $1 \dots n$ olarak numaralandırılmış $n$ ineği, toynaklarında fazla zaman geçirmektedir. Bunun sonucunda, Farmer John'un her sabah onları sağma sırasıyla ilgili karmaşık bir sosyal yapı geliştirmişlerdir. Haftalarca süren araştırmanın ardından, Farmer John bu yapının iki temel özelliğe dayandığını keşfetmiştir.

İlk olarak, ineklerin sosyal hiyerarşisi nedeniyle, bazı inekler sosyal statülerine bağlı olarak diğer ineklerden önce sağılmakta ısrar etmektedir. Örneğin, eğer inek $3$ 'ün statüsü en yüksek, inek $2$ 'nin statüsü ortalama ve inek $5$ 'in statüsü düşükse, inek $3$ inek $2$ 'den önce, inek $2$ de inek $5$ 'ten önce sağılmalıdır.
İkinci olarak, bazı inekler yalnızca sırada belirli bir konumda sağılmalarına izin verir. Örneğin, inek $4$ ikinci sırada sağılmakta ısrar edebilir.

Neyse ki, Farmer John ineklerini her zaman bu koşulların tümünü sağlayan bir sırayla sağabilmektedir.

Ne yazık ki, inek $1$ son zamanlarda hastalanmıştır, bu yüzden Farmer John onu mümkün olduğunca erken sağmak istemektedir, böylece ahıra geri dönüp çok ihtiyaç duyduğu dinlenmeyi alabilecektir. Farmer John'un sağma sırasında inek $1$ 'in işgal edebileceği en erken konumu belirlemesine yardımcı olun.

Giriş

İlk satır üç tam sayı içerir: $n$ , $m$ ve $k (2 \leq n \leq 100, 1 \leq m < n, 1 \leq k < n)$ k~(2 \le n \le 100, 1 \le m < n, 1 \le k < n): Farmer John'un $n$ ineği vardır, bunlardan $m$ tanesi bir sosyal hiyerarşi oluşturur ve $k$ tanesi sırada belirli konumlarda sağılmayı talep eder. İkinci satır $m$ tane farklı tam sayı $m_{i} (1 \leq m_{i} \leq n)$ m_i~(1 \le m_i \le n) içerir; bu satırda listelenen inekler, göründükleri sırayla sağılmalıdır. Sonraki $k$ satırın her biri iki tam sayı $c_{i}$ c_i ve $p_{i} (1 \leq c_{i}, p_{i} \leq n)$ p_i~(1 \le c_i, p_i \le n) içerir, bu da inek $c_{i}$ c_i'nin $p_{i}$ p_i konumunda sağılması gerektiği anlamına gelir.

Bu kısıtlamalar altında geçerli bir sağma sırasının var olduğu garanti edilmektedir.

Çıktı

Sağma sırasında inek $1$ 'in işgal edebileceği en erken konumu gösteren tek bir tam sayı yazdırın.

Örnekler

Örnek 1

Not

Bu örnekte, Farmer John'un $6$ ineği vardır ve inek $1$ hastadır. İnek $4$ 'ü inek $5$ 'ten önce, inek $5$ 'i de inek $6$ 'dan önce sağmalıdır. Ayrıca, inek $3$ ilk sırada, inek $5$ ise üçüncü sırada sağılmalıdır.

İnek $3$ ilk sırada sağıldığı ve inek $4$ , üçüncü sırada sağılan inek $5$ 'ten önce gelmesi gerektiği için, inek $4$ ikinci sırada sağılmalıdır. Böylece, inek $1$ için en erken konum dördüncü sıradır.