Phòng Đào tạo vừa đổi lịch thi một học phần của khoá có ~n~ sinh viên, đánh số từ ~1~ đến ~n~. Trong khoá có ~m~ cặp sinh viên là bạn bè của nhau (quan hệ bạn bè là hai chiều); cặp thứ ~j~ gồm hai sinh viên ~u_j~ và ~v_j~.

Tại phút ~0~ có đúng ~k~ sinh viên đọc được thông báo đổi lịch, ta gọi họ là các nguồn. Thông báo lan truyền như sau: nếu một sinh viên biết thông báo ở phút ~t~ thì đến phút ~t+1~ tất cả bạn bè của sinh viên đó đều biết thông báo. Người đã biết thông báo thì tiếp tục báo cho bạn bè ở mọi phút sau đó.

Yêu cầu

• Nếu đến một lúc nào đó cả ~n~ sinh viên đều biết thông báo: hãy tìm ~T~ là phút sớm nhất mà tại đó tất cả sinh viên đều đã biết thông báo, và đếm số sinh viên biết thông báo lần đầu tiên đúng vào phút ~T~;
• Ngược lại: hãy đếm số sinh viên không bao giờ biết thông báo.

Dữ liệu vào

• Dòng thứ nhất chứa ba số nguyên ~n~, ~m~ và ~k~;
• Dòng thứ hai chứa ~k~ số nguyên phân biệt – số hiệu của các nguồn;
• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~u_j~ và ~v_j~.

Kết quả ra

Ghi ra hai dòng:

• Nếu mọi sinh viên đều biết thông báo: dòng thứ nhất ghi ~T~, dòng thứ hai ghi số sinh viên biết thông báo lần đầu tiên đúng vào phút ~T~ (nếu ~T = 0~ thì đó chính là ~k~ nguồn);
• Ngược lại: dòng thứ nhất ghi ~-1~, dòng thứ hai ghi số sinh viên không bao giờ biết thông báo.

Ràng buộc

~1 \le k \le n \le 10^5~; ~0 \le m \le 2 \cdot 10^5~; ~1 \le u_j, v_j \le n~; ~u_j \ne v_j~; không có cặp bạn bè nào được liệt kê hai lần.

• Subtask 1 (15% số điểm – test 01–04): ~k = 1~, nguồn là sinh viên ~1~ và quan hệ bạn bè tạo thành một đường thẳng: ~m = n-1~, cặp thứ ~j~ là ~(j, j+1)~;
• Subtask 2 (20% số điểm – test 05–08): ~n \le 1000~ và ~m \le 2000~;
• Subtask 3 (20% số điểm – test 09–12): ~k = 1~;
• Subtask 4 (45% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

7 7 2
1 6
1 2
2 3
3 4
4 5
5 6
2 7
3 7

Kết quả ra mẫu 1

2
3

Dữ liệu vào mẫu 2

6 3 2
1 4
1 2
2 4
5 6

Kết quả ra mẫu 2

-1
3

Giải thích

Ví dụ thứ nhất: phút ~0~ có sinh viên ~1~ và ~6~ biết thông báo; phút ~1~ thêm sinh viên ~2~ (bạn của ~1~) và ~5~ (bạn của ~6~); phút ~2~ thêm sinh viên ~3~, ~7~ (bạn của ~2~) và ~4~ (bạn của ~5~). Đến phút ~T = 2~ cả ~7~ sinh viên đều đã biết, trong đó ~3~ sinh viên biết lần đầu đúng vào phút ~2~.

Ví dụ thứ hai: sinh viên ~2~ biết thông báo ở phút ~1~; các sinh viên ~3~, ~5~ và ~6~ không bao giờ biết thông báo.