Несмотря на то, что уже XXI век на дворе, СМИ в Моржландии не сильно распространены. Оповещение городов ведется с помощью гонцов которые могут путешествовать только по дорогам. Сеть дорог в Моржландии устроена так, что от каждого города до любого другого можно добраться ровно одним способом, и длины дорог равны между собой.
Решением правителя Северного Полюса было принято провести информационную реформу. Было решено выбрать несколько городов и назначить их областными центрами. На обслуживание областного центра приходится тратить k рыбликов (местная валюта) в год. Считается, что областной центр всегда имеет информацию о последних новостях.
Каждому городу, не являющемуся областным центром, было принято решение назначить областной центр, который будет отвечать за информированность этого города. В таком случае затраты на обслуживание равняются dlen рыбликам в год, где len — расстояние от города до соответствующего областного центра, измеряемое в количестве дорог, которые надо проехать.
Ваша задача минимизировать расходы на проведение реформы.
Выходные данные
В первой строке выведите минимальное количество рыбликов, затрачиваемых на обслуживание за один год. Во второй строке выведите n чисел, где i-ое число будет обозначать номер областного центра, который был назначен i-ому городу. Если i-й город сам является областным центром, то следует вывести число i.
Если решений несколько, выведите любое.