Существует неориентированное дерево, состоящее из \(n\) вершин, соединенных \(n-1\) двусторонним ребром. Также есть змея, находящаяся внутри этого дерева. Ее голова находится в вершине \(a\) и ее хвост находится в вершине \(b\). Тело змеи занимает все вершины на простом пути между вершинами \(a\) и \(b\).
Змея хочет узнать, может ли она развернуться, то есть переместить свою голову в вершину, где начинался хвост и переместить свой хвост в вершину, где начиналась голова. К сожалению, движения змеи ограничены структурой дерева.
За одну операцию змея может переместить свою голову в соседнюю вершину, которая не занята змеей в текущий момент. Когда это происходит, хвост змеи перемещается на одну вершину ближе к голове, то есть длина змеи не изменяется. Аналогично, змея может переместить свой хвост в соседнюю вершину, которая не занята змеей в текущий момент. Когда это происходит, голова змеи перемещается на одну вершину ближе к хвосту.
Будем обозначать позицию змеи, как \((h,t)\), где \(h\) — это номер вершины дерева, в которой находится голова и \(t\) — номер вершины дерева, где находится хвост. Змея сможет развернуться с помощью последовательности операций \((4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)\). Определите, сможет ли змея развернуться с помощью некоторой последовательности операций.
Выходные данные
Для каждого набора входных данных выведите «YES», если змея может развернуть себя и «NO», иначе.
Примечание
Первый набор входных данных изображен на картинке в тексте условия задачи.
Во втором наборе входных данных дерево имеет форму пути. Можно показать, что змея не сможет развернуться.
В третьем наборе входных данных, можно показать, что змея не сможет развернуться.
В четвертом наборе входных данных пример последовательности операций:
\((15,12)\to (16,11)\to (15,13)\to (10,14)\to (8,13)\to (4,11)\to (1,10)\)
\(\to (2,8)\to (3,4)\to (2,5)\to (1,6)\to (4,7)\to (8,6)\to (10,5)\)
\(\to (11,4)\to (13,8)\to (14,10)\to (13,15)\to (11,16)\to (12,15)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8 4 7
1 2
2 3
1 4
4 5
4 6
1 7
7 8
4 3 2
4 3
1 2
2 3
9 3 5
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
16 15 12
1 2
2 3
1 4
4 5
5 6
6 7
4 8
8 9
8 10
10 11
11 12
11 13
13 14
10 15
15 16
|
YES
NO
NO
YES
|