Thành phố X có tất cả ~n~ nút giao thông (đánh số từ ~1~ đến ~n~) và ~m~ con đường hai chiều (còn gọi là con phố) nối trực tiếp giữa một số cặp nút, không có con phố nào nối một nút giao thông với chính nó. Giữa hai nút giao thông khác nhau bất kì luôn có duy nhất một đường đi, có thể là đường đi trực tiếp hoặc không trực tiếp (đi qua các con phố khác).

Người dân đi lại trong thành phố bằng hệ thống xe Buýt công cộng. Việc di chuyển qua một con phố phải mất chi phí là ~1~ đồng coin. Thành phố muốn xây dựng lại hệ thống giao thông, trong đó sẽ chọn ra một nút làm nút trung tâm và chọn ~k~ con phố miễn phí (việc di chuyển sẽ không phải trả tiền khi đi trên con phố này).

Yêu cầu: Hãy lên phương án chọn nút giao thông trung tâm và ~k~ con phố miễn phí sao cho chi phí phải trả khi di chuyển từ tất cả các nút giao thông khác về nút trung tâm là nhỏ nhất.

Dữ liệu:

• Dòng 1: Chứa 3 số nguyên dương ~n~, ~m~ và ~k~ tương ứng là số nút giao thông, số con phố của cả thành phố và số con phố miễn phí (~1 \lt n \le 10^4, m \le 3.10^5, k \lt m~);
• ~m~ dòng tiếp theo, mỗi dòng chứa ~2~ số ~i, j~ có nghĩa là có con phố nối nút giao thông ~i~ và nút giao thông ~j~.

Kết quả:

• Ghi ra một số nguyên là chi phí (số đồng coin) tối thiểu phải trả khi di chuyển từ tất cả các nút giao thông khác về nút trung tâm.

Ví dụ:

Sample Input

13 12 3
1 2
2 3
2 8
7 8
7 5
5 4
5 6
8 9
8 10
10 11
10 12
10 13

Sample Output

11

Giải thích:

Có nhiều phương án giải quyết và đây là ~1~ phương án: ~5-7, 7-8, 8-10~ là những con phố miễn phí. Nút ~8~ là nút giao thông trung tâm. Chi phí tối thiểu là: ~11~.

Ràng buộc:

• Có ~25\%~ số test ứng với ~25\%~số điểm có ~n \le 30~;
• Có ~25\%~ số test ứng với ~25\%~ số điểm có ~30 \lt n \le 10^3~;
• Có ~50\%~ số test ứng với ~50\%~ số điểm có ~10^3 \le n \le 10^4~.