Trò chơi chiến tranh vũ trụ diễn ra ở một dải ngân hà có ~ n ~ hành tinh, đánh số từ ~ 0 ~ đến ~ n-1 ~. Một số hành tinh được kết nối với nhau bằng “hố đen”. Trụ sở của bạn nằm tại hành tinh ~ 0 ~ và của quân địch nằm tại hành tinh ~ 1 ~. Có hai loại hành tinh: Bạn đang sở hữu một hành tinh, hoặc bạn đang đe dọa một hành tinh nếu bạn không sở hữu nó, nhưng hành tinh đó nối trực tiếp với một hành tinh mà bạn đang sở hữu. Ban đầu bàn chỉ sở hữu hành tinh ~ 0 ~. Chiến thuật của bạn dự định sử dụng như sau: 1. Nếu bạn đang đe dọa hành tinh ~ 1 ~, nhiệm vụ kết thúc 2. Bạn tiến hành chiếm một hành tinh trong số những hành tinh bạn đang đe dọa. Hãy tìm phương án chiếm đóng hành tinh sao cho: + Bạn chiếm thêm ít hành tinh nhất có thể. Trong số các phương án thỏa mãn điều kiện 1, chọn phương án đe dọa nhiều hành tinh nhất có thể.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên ~ t ~ là số bộ test ~ (0 ≤ t ≤ 50) ~
• Dòng thứ hai chứa hai số nguyên ~ n ~ và ~ m ~ là số hành tinh và số hố đen.
• Dòng thứ ba chứa ~ m ~ xâu cách nhau bởi dấu cách. Mỗi xâu có dạng ~ “x, y” ~ với ~ x ~ và ~ y ~ là chỉ số hai hành tinh được kết nối qua hố đen. Dữ liệu đảm bảo mỗi cặp hành tinh được kết nối bởi không quá một hố đen.

Kết quả

Trên mỗi dòng đưa ra ~ “Case ~ #~d: x y” ~ với ~ d ~ là chỉ số test, ~ x ~ và ~ y ~ ứng với số hành tinh chiếm được và đe dọa trong phương án tối ưu

Ràng buộc

• Sub 1: ~ 2 ≤ n ≤ 36; 1 ≤ m ≤ 630 ~.
• Sub 2: ~ 2 ≤ n ≤ 400; 1 ≤ m ≤ 2000 ~.

Ví dụ:

Input 1

4
2 1
0,1
3 3
0,1 1,2 0,2
5 5
0,4 0,2 2,4 1,2 1,4
7 9
0,6 0,2 0,4 2,4 3,4 2,3 3,5 4,5 1,5 

Output 1

Case #1: 0 1
Case #2: 0 2
Case #3: 1 2
Case #4: 2 4