Алисе надоели обычные правила игры в догонялки, и она предложила Бобу немного их изменить. Теперь игра происходит на неориентированном корневом дереве из n вершин. Вершина 1 является корнем дерева.
Алиса начинает в вершине 1, а Боб — в вершине x (x ≠ 1). Ходы совершаются по очереди, Боб начинает. За один ход игрок может либо остаться в текущей вершине, либо перейти в соседнюю.
Игра завершается, когда Алиса приходит в вершину, в которой находится Боб. Алиса хочет минимизировать общее количество ходов, Боб хочет максимизировать.
Напишите программу, которая определит, сколько ходов продлится игра.
Выходные данные
Выведите общее количество ходов, которые будут совершены Алисой и Бобом.
Примечание
В первом примере дерево выглядит так:
Красная вершина — начальная позиция Алисы, синяя — Боба. Боб обеспечит самую долгую игру, если будет оставаться в вершине 3.
B: стоит в вершине 3
A: идет в вершину 2
B: стоит в вершине 3
A: идет в вершину 3
Во втором примере дерево выглядит так:
Ходы в оптимальной стратегии:
B: идет в вершину 3
A: идет в вершину 2
B: идет в вершину 4
A: идет в вершину 3
B: стоит в вершине 4
A: идет в вершину 4
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2
2 3
2 4
|
4
|
|
2
|
5 2
1 2
2 3
3 4
2 5
|
6
|