Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT128D - Trái tim của đất nước

Nước Graphia đang có chiến tranh. Đất nước này có nhiều thành phố. Các thành phố nối với nhau bởi các đường cao tốc. Mỗi thành phố có một số đội quân đang đóng ở đó. Bộ Quốc phòng Graphia a biết rằng để bảo vệ bất cứ thành phố nào thì cần số đội quân là K. Một thành phố được bảo vệ bởi các đội quân đóng tại đó và các đội quân đóng ở các thành phố có đường trực tiếp với thành phố đó. Với giả sử quân địch chỉ tấn công một thành phố tại một thời điểm.

Tuy nhiên, nếu một thành phố không thể được bảo vệ thì Bộ Quốc phòng phải xem như các đội quân ở đó sẽ bị bắt và không hỗ trợ được gì cho phòng thủ các thành phố khác. Trong trường hợp sau, với K=10, thành phố C có thể bị thất bại (sau khi dịch chiếm các thành phố có số quân là 4 ở xung quanh thành phố C). 

Người ta muốn tìm ra trái tim của đất nước là nhóm lớn nhất các thành phố có thể bảo vệ lẫn nhau, ngay cả khi các thành phố khác bị thất bại. 

Input

Có nhiều bộ test, mỗi bộ test gồm

  • Dòng 1 ghi 2 số N và K (3<=N<=1000; 0<=K<N).
  • N dòng tiếp theo mô tả các thành phố (đánh số từ 0): gồm số đội quân T đang đóng ở đó (0<=T<=10000) và số các thành phố nối với nó – M. Sau đó là M số nguyên cho biết các thành phố được nối với nó. Các đường là hai chiều và không có hai đường nào nối cùng một cặp thành phố với nhau, không có thành phố nào có đường đi đến chính nó.
  • Bộ test cuối cùng chứa 2 số 0

Output

Với mỗi bộ test, ghi ra màn hình 2 số nguyên: số thành phố trong vùng trái tim của đất nước và số đội quân trong vùng trái tim đó

Example

Input:

4 900

100 2 1 2

200 2 0 3

500 2 0 3

1000 2 1 2

4 900

100 3 1 2 3

200 3 0 3 2

500 3 1 3 0

1000 3 2 1 0

0 0 Output:

3 1700

4 1800

Được gửi lên bởi:adm
Ngày:2012-04-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC PYTHON3

hide comments
2014-05-28 23:47:12 Hat Dau Nho
cuối cùng cũng AC !
xem tren dt ko thay hinh :(

Last edit: 2014-05-29 07:22:24
2014-02-27 13:59:43 Black Hole
ko sub dc nua ah
2013-11-14 13:26:19 Just wanna one
sao chả thấy hình minh họa đâu cả. :(
2012-10-18 15:37:28 LOVE
Anh huu thang nhac toi em ak
2012-10-18 14:27:52 Vương Sỹ Huấn DH BK TP HCM
Sao lai co ca anh hung xa dieu o day ??
2012-10-16 14:34:01 1970


Last edit: 2013-11-20 11:47:15
2012-10-16 14:32:00 1970


Last edit: 2013-11-20 11:46:51
2012-10-16 14:29:05 1970


Last edit: 2013-11-11 15:50:43
2012-10-14 14:29:02 Vương Sỹ Huấn DH BK TP HCM
Minh van chua hieu cau tim may nguoi lam duoc ay sorry minh cung khong giup duoc
2012-10-13 09:14:04 Trần Vãn Dương D10CN2
Van chua hieu de ai lam duoc giup minh voi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.