Задача №113274. Демократия
В Котийской Республике процветает демократия: как главный демократ сказал, так и будет. В Республике есть n городов и k политических партий. Руководителем в каждом городе является представитель одной из партий.
Также в Республике широкое развитие получили информационные и нанотехнологии, в особенности их альянс "— новейшие локальные сети с нанотрафиком. Уже построены некоторые каналы связи между городами с использованием этой технологии, причём все города связаны (возможно, через промежуточные города). Технология слишком нова, поэтому набор каналов, необходимых для этого, минимален по количеству.
Главный демократ постановил провести всеобщий политический форум. С этой целью, кроме введения комендантского часа, было решено также выбрать k городов "— по одному с руководителем из каждой партии, "— а также построить дополнительные каналы связи, чтобы информация могла быть доставлена между выбранными городами, не проходя через города, не выбранные для форума. А для обеспечения полнейшей безопасности все каналы, ведущие к городам, не участвующим в форуме, должны быть разобраны и разворованы.
Официальное открытие форума, как всегда, состоялось вчера, поэтому требуется проложить каналы как можно быстрее. Государственный монополист, компания «КОТ и Ко», способна прокладывать или разворовывать только один канал в один момент времени, поэтому время, которое потребуется для завершения процесса, равно сумме времён прокладок и разворовываний каналов. Новейшие разработки в области информационных нанотехнологий позволяют построить один новый канал всего за одну минуту. Время, необходимое для разборки и разворовывания канала, также равно одной минуте, хотя нанотехнологии в этом случае ни при чём.
Посчитайте минимальное время, через которое поставленная задача может быть выполнена, а также выясните, какие города следует выбрать для форума и какие каналы связи нужно построить и разобрать.
В первой строке входного файла заданы целые числа n и k "— количество городов и политических партий в Республике ( 1 ≤ n ≤ 2000 , 1 ≤ k ≤ 10 ).
Во второй строке записано n целых чисел от 1 до k "— для каждого города номер партии, которой он принадлежит. Каждой партии принадлежит хотя бы один город.
Далее в ( n - 1) строке описаны существующие каналы связи: каждая из этих строк содержит два числа a i и b i , означающих, что существует канал связи между городами a i и b i . Города пронумерованы целыми числами от 1 до n .
В первой строке выведите единственное целое число "— минимально возможное время в минутах для завершения процесса. Далее выведите по одной строке для каждой минуты. Строка должна начинаться словом « build », если нужно построить канал, или словом « destroy », если канал нужно разобрать. Далее должны следовать два числа "— номера городов, между которыми прокладывается или разбирается канал. В последней строке выведите k чисел "— номера городов, участвующих в форуме. Если решений, на которые требуется минимальное время, несколько, можно вывести любое из них.
Решения, работающие при ограничениях n ≤ 200 и k ≤ 8 , будут оцениваться исходя из 60 баллов.
7 3 2 1 1 1 1 1 3 1 2 2 3 3 4 4 5 5 6 6 7
3 build 6 1 destroy 1 2 destroy 5 6 1 6 7