Xem tivi

Trong một khu dưỡng lão, có $N$ người già đang xem truyền hình. Các chương trình truyền hình bao gồm $M$ kênh được đánh số từ $1$ đến $M$. Mỗi người trong số họ có kênh mình yêu thích và có kênh mình không thích.

Nếu TV đang hiển thị một kênh không thích của một người nào đó, ông ấy sẽ đứng dậy, đi đến TV và thay đổi đến kênh yêu thích của mình và quay lại ghế xem tiếp. Nếu có nhiều người cùng không thích một kênh đang chiếu, thì người trẻ nhất trong số họ sẽ đứng dậy và chuyển qua kênh yêu thích của mình, phần còn lại sẽ vẫn ngồi yên.

Tất nhiên, sau khi có một sự thay đổi của kênh truyền hình, có thể là người khác thấy kênh mới là kênh không thích nên anh sẽ thay đổi kênh đó sang kênh khác. Với thực tế như vậy, quá trình chuyển kênh truyền hình có thể diễn ra vô thời hạn.

Yêu cầu: Cho trước danh sách những kênh yêu thích và không thích của tất cả $N$ người, hãy xác định số lần chuyển kênh để đến một kênh nào đó tất cả mọi người cùng chấp nhận ngồi xem (tức là không có ai không thích kênh đó). Nếu ngay kênh ban đầu đã không có ai không thích thì số lần chuyển kênh là $0$.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$ và $P$ $(1\le N,M\le {10}^5,1\le P\le M)$: số người nghỉ hưu, số lượng các kênh truyền hình và kênh ban đầu hiển thị trên TV;
• Mỗi dòng trong số $N$ dòng tiếp theo chứa $2$ số nguyên $a_i$ và $b_i$ $(1\le a_i,b_i\le M,a_i\ne b_i)$: kênh yêu thích và kênh không thích của mỗi người;
• Sự sắp xếp thứ tự của người xem truyền hình ở đầu vào là từ trẻ nhất đến già nhất (người thứ $1$ trẻ nhất).

Dữ liệu ra

Một dòng duy nhất là số lần thay đổi kênh. Nếu những sự thay đổi liên tục và vô thời hạn thì đưa ra $-1$.

Ràng buộc

• $1\le N,M\le {10}^5$.
• $1\le P\le M$.
• $1\le a_i,b_i\le M$, $a_i\ne b_i$.

Subtasks

• Subtask 1 ($50\%$ số test đầu tiên): $1\le N,M\le 1000$.
• Subtask 2 ($50\%$ số test còn lại): không có ràng buộc gì thêm.

Mỗi test có số điểm như nhau.

Ví dụ