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.|

VMCUT - Cắt đồ thị

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmcut


Cho một đơn đồ thị vô hướng G = (V, E)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 Hv 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(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 NM (1 ≤ N ≤ 200, 0 ≤ MN * (N - 1) / 2).
  • M dòng tiếp theo, mỗi dòng chứa 2 số nguyên uv thể hiện đồ thị có cạnh nối trực tiếp giữa uv.
  • 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

Được gửi lên bởi:VOJ Team
Ngày:2015-07-20
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:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM15 - Nguyễn Vương Linh

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.