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.

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.

Input

• 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à 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.

Output

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~.

Scoring

Sample Input 1

4 5 2
1 3
2 3
3 2
5 1

Sample Output 1

3

Sample Input 2

3 3 1
1 2
2 3
3 1

Sample Output 2

-1

Notes

TV đang chiếu kênh ~2~, người thứ ~3~ không thích nên chuyển sang kênh ~3~, có ~2~ người không thích kênh ~3~ nên người ~1~ (vì anh trẻ hơn) chuyển sang kênh ~1~, người thứ ~4~ không thích kênh ~1~ nên chuyển sang kênh ~5~. Lúc này mọi người đều chấp nhận kênh này. Như vậy, đã có ~3~ lần chuyển kênh để đến được kênh ~5~.