Chia vương quốc

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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 \leq n, k \leq 10^{6}$
$0 \leq m \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 3 2 1 2 2 3 3 1	0	Chỉ có một tỉnh duy nhất, không cần thêm đường hay đường hầm.
4 2 2 1 2 3 4	0	Hai tỉnh ${1, 2}$ và ${3, 4}$ . Xây một đường hầm giữa thành phố 1 và 3 là đủ.
4 0 2	1	Bốn tỉnh, mỗi tỉnh một thành phố nên mỗi tỉnh chỉ có thể nối tối đa $1$ đường hầm. Cần xây thêm 1 con đường (ví dụ nối $1$ – $2$ ) rồi dùng $2$ đường hầm $1$ – $3$ và $2$ – $4$ .

Bình luận

Không có bình luận tại thời điểm này.