Đồ thị liên thông

Trong một buổi nghiên cứu về tâm lý học, FullHouse Dev được đưa ra một bài toán thú vị về đồ thị. Họ nhận thấy rằng việc phân tích các thành phần liên thông trong đồ thị có thể giúp hiểu rõ hơn về mối quan hệ giữa các cá nhân trong một nhóm.

Bài toán

Cho một đồ thị có \(n\) đỉnh và \(m\) cạnh. Nhiệm vụ là tính số cạnh tối đa có thể loại bỏ khỏi đồ thị sao cho đồ thị còn chính xác \(k\) thành phần liên thông.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) (theo thứ tự đó).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u\) và \(v\) thể hiện có một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\).
• Đảm bảo đồ thị không có cạnh trùng và không có cạnh nối một đỉnh với chính nó.

OUTPUT FORMAT:

• In ra số cạnh tối đa có thể loại bỏ để đồ thị có đúng \(k\) thành phần liên thông.
• Nếu đồ thị ban đầu có nhiều hơn \(k\) thành phần liên thông, in ra \(-1\).

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(0 \leq m \leq 10^5\)
• \(1 \leq k \leq n\)

Ví dụ

INPUT

4 3 2
1 2
2 3
1 3

OUTPUT

1

Giải thích

Ban đầu, đồ thị có \(1\) thành phần liên thông. Chúng ta có thể loại bỏ \(1\) cạnh để tạo ra đúng \(2\) thành phần liên thông.