Маша хочет открыть свою пекарню и печь пирожки в одном из n городов, пронумерованных от 1 до n. Также существует m двунаправленных дорог, каждая из которых соединяет некоторую пару городов. Чтобы печь пирожки, Маше нужно наладить регулярные поставки муки со склада. Всего существует k складов, расположенных в различных городах с номерами a1, a2, ..., ak.
К сожалению, законы страны, в которой живет Маша, не позволяют открывать пекарню в любом из городов, где есть склад. Открыть ее можно только в одном из остальных n - k городах, при этом, само собой, за доставку муки нужно платить — за каждый километр пути от склада до пекарни Маша заплатит 1 рубль.
Формально, Маша заплатит x рублей, если она откроет пекарню в городе b (ai ≠ b для любого 1 ≤ i ≤ k) и выберет склад в городе s (s = aj для некоторого 1 ≤ j ≤ k), а между городами b и s существует путь по дорогам суммарной длины x (если путей несколько, Маша вправе выбирать, какой именно путь будет использован).
Маша — крайне бережливый и рациональный человек. Ее интересует тот город, при открытии пекарни в котором (и выборе одного из k складов и пути между городом с пекарней и городом со складом) платить за доставку ей придется меньше всего. Помогите Маше найти сумму, которую она заплатит в этом случае.
Выходные данные
В единственной строке выведите минимальную цену, которую придется заплатить Маше за доставку муки.
Если открыть пекарню, удовлетворив необходимым условиям, ни в одном из n городов невозможно, в единственной строке выведите - 1.