\(N\) cô bò của bác nông dân John (\(2 \leq N \leq 100\)), như thường lệ được đánh số thuận tiện từ \(1 \ldots N\), tình cờ có quá nhiều thời gian rảnh. Vì vậy, chúng đã xây dựng một cấu trúc xã hội phức tạp liên quan đến thứ tự bác nông dân John vắt sữa chúng vào mỗi buổi sáng. Sau nhiều tuần nghiên cứu, ông phát hiện cấu trúc này dựa trên hai đặc điểm chính.

Thứ nhất, do hệ thống thứ bậc xã hội của đàn bò, một số cô bò nhất quyết phải được vắt sữa trước những cô bò khác dựa trên địa vị xã hội của từng cô. Ví dụ, nếu bò 3 có địa vị cao nhất, bò 2 có địa vị trung bình và bò 5 có địa vị thấp, thì bò 3 phải được vắt sữa sớm nhất, sau đó đến bò 2 và cuối cùng là bò 5.

Thứ hai, một số cô bò chỉ chấp nhận được vắt sữa tại một vị trí nhất định trong thứ tự. Ví dụ, bò 4 có thể nhất quyết đòi được vắt sữa ở vị trí thứ hai trong toàn đàn.

May mắn thay, bác nông dân John luôn có thể vắt sữa đàn bò theo một thứ tự thỏa mãn tất cả các điều kiện này.

Không may, gần đây bò 1 bị ốm, nên bác nông dân John muốn vắt sữa cô ấy sớm nhất có thể để cô ấy trở về chuồng và nghỉ ngơi đầy đủ. Hãy giúp ông xác định vị trí sớm nhất mà bò 1 có thể xuất hiện trong thứ tự vắt sữa.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) (\(1 \leq M < N\)) và \(K\) (\(1 \leq K < N\)), cho biết bác nông dân John có \(N\) cô bò, \(M\) cô trong số đó đã tự sắp xếp thành một hệ thống thứ bậc xã hội, và \(K\) cô yêu cầu được vắt sữa tại một vị trí cụ thể trong thứ tự. Dòng tiếp theo chứa \(M\) số nguyên đôi một khác nhau \(m_i\) (\(1 \leq m_i \leq N\)). Các cô bò trên dòng này phải được vắt sữa theo đúng thứ tự xuất hiện trên dòng. Mỗi dòng trong \(K\) dòng tiếp theo chứa hai số nguyên \(c_i\) (\(1 \leq c_i \leq N\)) và \(p_i\) (\(1 \leq p_i \leq N\)), cho biết bò \(c_i\) phải được vắt sữa ở vị trí \(p_i\).

Bảo đảm rằng với các ràng buộc này, bác nông dân John có thể xây dựng một thứ tự vắt sữa hợp lệ.

Dữ liệu ra

In ra vị trí sớm nhất mà bò 1 có thể đứng trong thứ tự vắt sữa.

Ví dụ

6 3 2
4 5 6
5 3
3 1

4

Nguồn

USACO 2018 US Open Contest, Bronze — Milking Order

Tác giả bài toán: Jay Leeds.