Trong phòng nghỉ giải lao có ~ n ~ người đang xem ti vi. Chương trình ti vi có ~ m ~ kênh, đánh số từ 1 đến ~ m ~. Mỗi người có một kênh thích nhất và một kênh ghét nhất. Nếu tivi đang phát kênh mà một người nào đó ghét, người này sẽ đứng lên, đi tới tivi và chuyển đến kênh mình thích nhất sau đó quay về chỗ ngồi. Nếu nhiều người cùng ghét kênh đang phát, người trẻ nhất trong những người này sẽ đứng lên, đi tới ti vi để chuyển tới kênh mình thích nhất.

Cho danh sách kênh thích nhất và ghét nhất của ~ n ~ người. Hiện tại, ti vi đang phát kênh ~ p ~. Mọi người sẽ hài lòng nếu không phải xem kênh mình ghét nhất. Hãy xác định số lần chuyển kênh ít nhất để mọi người đều hài lòng.

Dữ liệu vào

• Dòng đầu tiên là 3 số nguyên ~ n, m, p ~ lần lượt là số người, số kênh và kênh đang phát trên ti vi.
• ~ n ~ dòng sau, dòng thứ ~ i ~ chứa một cặp số nguyên dương ~ a_i, b_i ~ là kênh thích nhất và ghét nhất của người thứ ~ i ~ ~ (a_i, b_i ≤ m, a_i ≠ b_i) ~. Thứ tự liệt kê lần lượt từ người trẻ nhất đén người già nhất trong phòng.

Kết quả

Đưa ra một số nguyên duy nhất là số lần chuyển kênh cần thiết để làm hài lòng tất cả mọi người. Nếu không chuyển kênh lần nào hoặc không tồn tại cách chuyển kênh làm hài lòng tất cả mọi người thì đưa ra -1.

Ràng buộc

• ~ 1≤ n, m ≤ 10^5 ~
• ~ 1 ≤ p ≤ m ~

Ví dụ:

Input 1

3 4 2
1 2
2 3
3 2 

Output 1

1