Алгоритм BFS определяется следующим образом.
- Алгоритм выполняется над некоторым неориентированным графом, вершины которого пронумерованы от \(1\) до \(n\). Инициализируем \(q\) как новую очередь, содержащую только вершину \(1\), также пометим вершину \(1\) как использованную.
- Извлечем вершину \(v\) из начала очереди \(q\).
- Напечатаем номер вершины \(v\).
- Переберем в произвольном порядке все вершины \(u\) такие, что \(u\) является соседом \(v\) и ещё не помечена как использованная. Пометим вершину \(u\) как использованную и добавим в конец очереди \(q\).
- Если очередь не является пустой, продолжим выполнение с шага 2.
- В противном случае закончим.
Так как порядок обхода соседей в каждой вершине не является фиксированным, то для данного графа BFS может вывести несколько различных последовательностей.
В данной задаче вам нужно проверить, может ли данная последовательность соответствовать какому-то запуску BFS на заданном дереве, начиная с вершины \(1\). Деревом называется неориентированный граф, в котором между каждой парой вершин есть ровно один простой путь.
Выходные данные
Выведите «Yes» (без кавычек), если порядок вершин соответствует какому-то корректному BFS на данном дереве, и «No» (без кавычек) иначе.
Вы можете выводить каждую из букв в любом регистре (строчную или заглавную).
Примечание
Оба теста из примеров содержат одинаковое дерево.
Для этого дерева существует два возможных порядка вершин, соответствующих какому-то запуску BFS.
- \(1, 2, 3, 4\),
- \(1, 3, 2, 4\).
Порядок вершин \(1, 2, 4, 3\) не может получится в результате BFS.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
2 4
1 2 3 4
|
Yes
|
|
2
|
4
1 2
1 3
2 4
1 2 4 3
|
No
|