Шапур победил Валериана. Эта победа была так важна, что Шапур решил вырезать на скале сцену поражения Валериана. Теперь ему нужно было найти наилучшее место и увековечить там свою победу!
Он решил посетить все n городов Персии чтобы найти наиболее подходящую скалу. Но недавняя война утомила его, и он не хотел много путешествовать. Поэтому он хотел посетить каждый из этих n городов хотя бы один раз. При этом пройденное расстояние должно быть как можно меньше. Персидские города соединены двусторонними дорогами. Из каждого города можно дойти до любого другого, причем единственным способом.
Все города пронумерованы от 1 до n. Шапур сейчас в городе 1, и он хочет посетить все остальные города, пройдя как можно меньше. Шапур может закончить свое путешествие в любом городе.
Найдите расстояние, которое Шапур пройдет.
Выходные данные
Выведите одно число — минимальную длину пути Шапура.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
2 3 4
|
7
|
|
2
|
3
1 2 3
1 3 3
|
9
|