D. Корректный BFS?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алгоритм BFS определяется следующим образом.

  1. Алгоритм выполняется над некоторым неориентированным графом, вершины которого пронумерованы от $$$1$$$ до $$$n$$$. Инициализируем $$$q$$$ как новую очередь, содержащую только вершину $$$1$$$, также пометим вершину $$$1$$$ как использованную.
  2. Извлечем вершину $$$v$$$ из начала очереди $$$q$$$.
  3. Напечатаем номер вершины $$$v$$$.
  4. Переберем в произвольном порядке все вершины $$$u$$$ такие, что $$$u$$$ является соседом $$$v$$$ и ещё не помечена как использованная. Пометим вершину $$$u$$$ как использованную и добавим в конец очереди $$$q$$$.
  5. Если очередь не является пустой, продолжим выполнение с шага 2.
  6. В противном случае закончим.

Так как порядок обхода соседей в каждой вершине не является фиксированным, то для данного графа BFS может вывести несколько различных последовательностей.

В данной задаче вам нужно проверить, может ли данная последовательность соответствовать какому-то запуску BFS на заданном дереве, начиная с вершины $$$1$$$. Деревом называется неориентированный граф, в котором между каждой парой вершин есть ровно один простой путь.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), обозначающее количество вершин в дереве.

Следующие $$$n - 1$$$ строк задают рёбра дерева. Каждая из них содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$) — концы соответствующего ребра дерева. Гарантируется, что заданный граф является деревом.

Последняя строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — последовательность, которую вам нужно проверить.

Выходные данные

Выведите «Yes» (без кавычек), если порядок вершин соответствует какому-то корректному BFS на данном дереве, и «No» (без кавычек) иначе.

Вы можете выводить каждую из букв в любом регистре (строчную или заглавную).

Примеры
Входные данные
4
1 2
1 3
2 4
1 2 3 4
Выходные данные
Yes
Входные данные
4
1 2
1 3
2 4
1 2 4 3
Выходные данные
No
Примечание

Оба теста из примеров содержат одинаковое дерево.

Для этого дерева существует два возможных порядка вершин, соответствующих какому-то запуску BFS.

  • $$$1, 2, 3, 4$$$,
  • $$$1, 3, 2, 4$$$.

Порядок вершин $$$1, 2, 4, 3$$$ не может получится в результате BFS.