Нечётный разрез
Нечётный разрез
Задан связный неориентированный граф из n вершин и m рёбер. Рёбрам приписаны неотрицательные целые веса. Известно, что n чётное. Найдите разбиение множества вершин на множества A и B такое, чтобы выполнялись следующие условия:
A
B =
,
|A| и |B| - нечётные числа,
суммарный вес рёбер, один конец которых находится в A, а другой - в B, минимален.
Giriş verilənləri
В первой строке находится два числа - n и m (1 ≤ n ≤ 200, 1 ≤ m ≤ 2000). В следующих m строках находятся описания рёбер графа. Каждая из них содержит номера концов ребра и его вес - целое число от 0 до 10^5, включительно. Вершины графа нумеруются с единицы. Гарантируется, что в графе нет петель, хотя могут быть кратные рёбра.
Çıxış verilənləri
Выведите в первой строке искомый минимальный вес рёбер.
Во второй строке выведите размер множества A.
В третьей строке выведите номера вершин, которые входят в это множество.
Nümunə
6 9 6 1 1 6 2 7 2 1 1 1 4 2 2 4 4 1 3 3 3 4 1 3 5 6 4 5 2
7 3 1 3 5