Дано дерево (связный неориентированный граф без циклов), его вершины пронумерованы от 1 до n, длина i-го ребра wi. В вершине s стоит полицейский, также в вершинах x1, x2, ..., xm (xj ≠ s) расположены m преступников.
Полицейский ходит по ребрам со скоростью 1, преступники могут перемещаться со сколь угодно большой скоростью. Если преступник в какой-то момент находится в одной точке с полицейским, его мгновенно ловят. Определите время, за которое можно поймать всех преступников, если преступники и полицейский действуют оптимально (т.е. преступники максимизируют это время, а полицейский — минимизирует). В любой момент времени все знают текущие положения всех остальных людей.
Выходные данные
Если полицейский не сможет поймать всех преступников, выведите в единственную строку «Terrorists win» (без кавычек).
Иначе выведите одно число — время, за которое полицейский поймает всех преступников.
Примечание
В первом примере один из оптимальных сценариев такой. Преступник 2 перемещается в вершину 3, а преступник 4 — в вершину 4. Полицейский идет в вершину 4 и ловит двух преступников. После этого преступник 1 перемещается в вершину 2. Полицейский идет в вершину 3 и ловит преступника 2, потом идет в вершину 2 и ловит оставшегося преступника.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 2
1 3 1
1 4 1
2
4
3 1 4 1
|
8
|
|
2
|
6
1 2 3
2 3 5
3 4 1
3 5 4
2 6 3
2
3
1 3 5
|
21
|