#1148. STAR - Đồ thị hình sao

Một đồ thị dạng “sao” có loại đỉnh: đỉnh tâm và đỉnh cánh, và có đúng cạnh nối đỉnh tâm với mỗi đỉnh cánh , là một số cho trước).

Cho một đồ thị vô hướng, bạn phải tìm một số đồ thị con, mỗi đồ thị con là một đồ thị “sao” mà không có đồ thị con nào có đỉnh chung. Mục tiêu là chọn các đồ thị con sao cho số đỉnh được phủ là nhiều nhất.

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên là số bộ test ;
• bộ test tiếp theo, mỗi bộ gồm ba số (số đỉnh, số cánh nhiều nhất của một sao và số cạnh) ;
• dòng tiếp theo, mỗi dòng gồm hai số thể hiện có cạnh nối hai chiều giữa đỉnh và . Chú ý rằng đồ thị không có cạnh trùng và không có đỉnh tự nối với chính nó. Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra dòng, mỗi dòng gồm một số nguyên duy nhất là số đỉnh tối đa được phủ bởi các đồ thị sao.

Ví dụ:

Dữ liệu vào:

2
8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
6 3 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5

Dữ liệu ra:

6
6

Giải thích:

• Test : Hình vẽ cho đồ thị của test này bên dưới. Bởi , mỗi đồ thị sao có tối đa cánh nên mỗi sao có thể phủ tối đa nút. Ta có thể phủ nút của đồ thị này với sao: một sao có tâm là và cánh là và , sao kia có tâm là với và là cánh. Không có sao nào khác được tạo thêm. Mỗi test case có thể có nhiều cách kết hợp sao khác nhau.

• Test : Hình vẽ cho test này phía dưới. Ta có thể phủ đỉnh với sao. Một sao có tâm là với cánh là và , sao còn lại có tâm là và cánh là và .

Giới hạn:

• số điểm có .