id="đường-ống-thoát-nước3842eb31b9f015ae4ce1-duongong.">Đường ống thoát nước (duongong.*)

Hệ thống thoát nước ngầm hiện đại của Vũng Tàu gồm \(n\) chốt được đánh số từ \(1\) đến \(n\) với \(m\ \)đường ống hai chiều nối giữa các cặp chốt có dạng \((i,j)\) với \(i
eq j\) và \(1 \leq i,j \leq n\). Ban đầu, các chốt trong hệ thống được đóng nắp và nước bên ngoài không thể chảy vào hệ thống. Khi có một chốt \(x\) được mở nắp, dòng nước bên ngoài sẽ chảy đến các chốt khác có đường ống thông với chốt \(x\) giúp giảm bớt ngập cho thành phố.

Nhà quản lí muốn mở nắp của không quá \(k(1 \leq k \leq n)\) chốt sao cho có thể dẫn nước từ bên ngoài vào, và thông qua các đường ống để dẫn nước sang nhiều chốt nhất có thể. Mặt khác, để giảm chi phí vận hành, các chốt được mở nắp phải có cùng số lượng đường ống nối đến trực tiếp.

Yêu cầu: Cho biết dòng nước có thể chảy đến được nhiều nhất là bao nhiêu chốt?

Dữ liệu:

• Dòng đầu chứa ba số \(n,m,k\left( 1 \leq k \leq n \leq 10^{5};0 \leq m \leq \left( \frac{n(n - 1)}{2},10^{5} \right)\ \right)\);

• Trong \(m\) dòng tiếp theo, mỗi dòng chứa cặp số \(i,j\) cho biết có đường ống nối trực tiếp giữa chốt \(i\) và \(j(i
  eq j;1 \leq i,j \leq n)\). Dữ liệu đảm bảo giữa cặp chốt \((i,j)\) có nhiều nhất 1 đường ống nối trực tiếp.

Kết quả:

+ Một số nguyên là số lượng chốt nhiều nhất mà nước có thể chảy đến khi mở nắp không quá \(k\) chốt và đảm bảo các chốt được mở phải có cùng số lượng đường ống nối trực tiếp (có thể cùng bằng 0).

Ví dụ:

Ràng buộc:

• Có 25% số test thỏa: \(k = 1\);

• Có 25% số test thỏa: \(1 \leq n \leq 100\);

• Có 50% số test không có ràng buộc gì thêm.