Несвязное множество

Помогите написать программу: Пусть задан некоторый неориентированный вершинно-взвешенный граф , состоящий из вершин и ребер, при этом каждая вершина характеризуется натуральным числом из множества , соответствующим «ценности» вершины.

Смежными называются вершины, имеющие общее ребро.

Несвязным множеством вершин называется такое подмножество вершин , что никакие две вершины из этого множества не являются смежными.

Ценностью множества вершин называется сумма ценностей всех вершин, входящих в это множество.

Задача

Ваша задача – выбрать из заданного графа несвязное множество вершин таким образом, чтобы ценность данного множества была как можно больше.

Технический регламент

<Число вершин>

<Ценность первой вершины> <Ценность второй вершины> … <Ценность последней вершины>

<Число ребер>

<Первая вершина первого ребра> <Вторая вершина первого ребра>

<Первая вершина второго ребра> <Вторая вершина второго ребра>

<Первая вершина третьего ребра> <Вторая вершина третьего ребра>

ответ

<Первая вершина последнего ребра> <Вторая вершина последнего ребра>

<Число выбранных вершин>

<Номер первой выбранной вершины> <Номер второй выбранной вершины> … <Номер последней выбранной вершины>

Обратите внимание на тот факт, что вершины нумеруются с единицы

Для уточнения деталей обратитесь к примеру.

Вот пример

• 5
• 10 6 6 1 1
• 4
• 1 2
• 3 1
• 3 5
• 1 4

Ответ:

• 2
• 1 5