У Cirno_9baka есть дерево с \(n\) вершинами. Он готов поделиться им с вами, что означает, что вы можете на нем оперировать.
Изначально в вершине \(1\) дерева стоят две шахматные фигуры. За один шаг вы можете выбрать любую фигуру и переместить ее в соседнюю вершину. Вам также дано целое число \(d\). Вам нужно выполнить следующее условие: расстояние между двумя фигурами всегда должно не превышать \(d\).
У каждой из этих двух фигур есть последовательность вершин, которые они должны пройти в любом порядке, и, в конце концов, они должны вернуться в корень. Как любознательный мальчик, он хочет узнать минимальное количество шагов, которое для этого необходимо сделать.
Выходные данные
Выведите одно целое число — минимальное количество шагов, которые необходимо сделать.
Примечание
В первом примере, вот одна возможная последовательность шагов длиной \(6\).
Вторая фигура перемещается по маршруту \(1 \to 2 \to 4 \to 2 \to 1\).
Затем, первая фигура перемещается по маршруту \(1 \to 3 \to 1\).
Во втором примере, вот одна возможная последовательность шагов длиной \(8\):
Первая фигура перемещается по маршруту \(1 \to 2 \to 3\).
Затем, вторая фигура перемещается по маршруту \(1 \to 2\).
Затем, первая фигура перемещается по маршруту \(3 \to 4 \to 3 \to 2 \to 1\).
Затем, вторая фигура перемещается по маршруту \(2 \to 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
1 3
2 4
1 3
1 4
|
6
|
|
2
|
4 2
1 2
2 3
3 4
4 1 2 3 4
1 1
|
8
|