Chia vương quốc

Vương quốc của Vasya gồm $n$ thành phố và $m$ con đường hai chiều giữa các thành phố. Hai thành phố thuộc cùng một tỉnh nếu và chỉ nếu có thể đi từ thành phố này sang thành phố kia chỉ bằng các con đường (mỗi tỉnh tương ứng với một thành phần liên thông của đồ thị).

Vasya muốn xây dựng thêm các đường hầm (cũng là cạnh hai chiều) sao cho sau khi xây xong, toàn bộ vương quốc trở thành liên thông (tức là từ bất kỳ thành phố nào cũng có thể đến được mọi thành phố khác bằng các con đường và đường hầm). Có hai ràng buộc về đường hầm:

• Mỗi thành phố được nối với không quá một đường hầm.
• Mỗi tỉnh được nối với không quá $k$ đường hầm.

Tuy nhiên, mạng lưới đường hầm thoả mãn các ràng buộc trên có thể không tồn tại với cấu hình hiện tại. Vasya có thể xây thêm các con đường mới giữa các thành phố nhằm hợp nhất các tỉnh (đường mới có thể nối hai thành phố thuộc các tỉnh khác nhau, biến chúng thành cùng một tỉnh). Hãy xác định số con đường mới tối thiểu cần xây để mạng lưới đường hầm thoả mãn ràng buộc tồn tại.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ — một con đường nối hai thành phố $u$ và $v$.

Không có con đường nào nối một thành phố với chính nó, và giữa hai thành phố bất kỳ có tối đa một con đường.

Dữ liệu ra

In ra một số nguyên duy nhất — số con đường mới tối thiểu cần xây.

Ràng buộc

• $1\le n,k\le {10}^6$
• $0\le m\le {10}^6$

Ví dụ