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ể.
Input
- Dòng ~1~: chứa ~2~ số nguyên dương ~N~ và ~M~ ~\left(1 \leq N \leq 200, 0 \leq M \leq \frac{N \times (N - 1)}{2}\right)~.
- ~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.
Cách tính điểm
Với mỗi test:
- Gọi ~D1(H)~ là giá trị ~D(H)~ của bạn, ~D2(H)~ là giá trị ~D(H)~ của BTC, ~P~ là điểm của 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à: ~\min \left(\frac{D1(H)}{D2(H)} \times P \times 95\%, P \right)~.
- Nếu tập ~H~ của bạn không hợp lệ, bạn đuợc 0 điểm.
Sample Input
5 6
1 2
2 3
3 1
2 4
3 5
4 5
Sample Output
4
2
2 3
Bình luận