Алгоритмы с возвратом

Задача сложная, по этому и прошу помощи.

Безопасные пути.
В некотором царстве есть система дорог, представляющая собой неориентированный граф. Каждая дорога соединяет два различных города. Между двумя городами может быть не более одной дороги. Известно, что с течением времени каждая дорога в этом царстве приобрела один из трех статусов. Первый – дороги, на которых регулярно происходят грабежи проезжающих дилижансов(далее – Д1), второй – дороги, на которых стоит царская охрана (далее – Д2) и третий – статус нейтральной дороги (далее – Д3). Поэтому население данной страны делится на два слоя – добропорядочных граждан и бандитов. Добропорядочные граждане данной страны ходят только по дорогам Д2 и Д3, а бандиты по дорогам Д1 и Д3. Так как царская казна тратит очень много денег на содержание дорог, то царь решил удалить максимальное количество дорог так, чтобы можно было добраться из любого города в любой другой как добропорядочному гражданину, так и грабителю. Ваша задача – найти максимальное количество дорог, которые можно удалить, а также их номера в соответствии с требованиями царя.
Формат входных данных. Ввод данных – из файла input.txt. В первой строке этого файла записано число N – количество городов(1<=N<=1000), а затем число М – количество дорог в царстве (1<=M<=10000). Каждая из последующих М строк содержит по три числа, которые описывают ровно одну дорогу: первые два числа задают номера городов, которые они соединяют, а третье статус дороги: 1 – Д1, 2 – Д2, 3 – Д3. Между любыми двумя городами существует не более одной дороги.
Формат выходных данных. Первая строка выходного файла output.txt должна содержать количество удаленных дорог, а во второй строке перечислены их номера, если таковые имеются. Дороги нумеруются в том порядке, в каком они были заданы во входном файле. Если решений несколько, то можно выдать любое из них. Если решения нет, выдать: -1.

0

царь решил удалить максимальное количество дорог так, чтобы можно было добраться из любого города в любой другой как добропорядочному гражданину, так и грабителю.

Вот интересно - с чего бы царю заботиться о грабителях ?
Задача интересная, но я бы переформулировал ее так:
какое минимальное число дорог нужно, чтобы всем можно было добраться из города в город.

0

Ну от этого сложность задачи не упрощается )

0