VNOI Marathon 2015

Cho một đơn đồ thị vô hướng G = (V, E) có N đỉnh và M cạnh. Với mỗi tập con H của V, gọi G(H) là đồ thị thu được từ việc xoá tất cả các đỉnh và các cạnh có ít nhất 1 đầu mút không thuộc H. Tập H được gọi là liên thông, nếu như G(H) liên thông. Gọi D(H) là giá trị lát cắt ứng với H: số lượng cạnh (u, v) thoả mãn 1 trong 2 đỉnh thuộc tập H, và đỉnh còn lại không thuộc tập H (u thuộc H và v không thuộc H, hoặc v thuộc H và u không thuộc H). Nói cách khác, D(H) là số cạnh tối thiểu cần xoá sao cho H và (G - H) không còn liên thông với nhau (G - H) là đồ thị nhận được khi xóa các đỉnh của H và các cạnh tương ứng ra khỏi G).

Xác định tập H liên thông sao cho D(H) lớn nhất có thể.

Cách tính điểm:

• Với mỗi test: Nếu giá trị D(H) và tập H của bạn hợp lệ, điểm của bạn sẽ là D(H)_bạn / D(H)_{ban tổ chức}. Ngược lại, bạn đuợc 0 điểm.

Input

• Dòng 1: chứa 2 số nguyên dương N và M (1 ≤ N ≤ 200, 0 ≤ M ≤ N * (N - 1) / 2).
• M dòng tiếp theo, mỗi dòng chứa 2 số nguyên u và v thể hiện đồ thị có cạnh nối trực tiếp giữa u và v.
• Dữ liệu đảm bảo không có cạnh nào xuất hiện 2 lần trong input
  

Output

• Dòng 1: Giá trị của D(H).
• Dòng 2: Kích thước tập H.
• Dòng 3: Những đỉnh thuộc tập H, mỗi số cách nhau bởi một khoảng trắng.

Chấm điểm

• Trong quá trình thi, bài của bạn được chấm với 20% test. Sau khi kỳ thi kết thúc, bài của bạn sẽ được chấm lại với toàn bộ 100% test.
• Chú ý, test ví dụ phía dưới không nằm trong 20% test.

Ví dụ

Input

5 6
1 2
2 3
3 1
2 4
3 5
4 5

Output 1

4
2
2 3

Output 2

2
3
1 2 3