410166: GYM103967 B Иерархия цитадели

B. Иерархия цитаделиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Как известно, в Цитадели Риков обитает бесчисленное множество Риков и Морти (а именно — $$$n$$$ Риков и $$$m$$$ Морти). Чтобы в новой Цитадели не было полного хаоса, было решено построить четкую иерархию, благодаря которой всегда можно будет быстро определить какой Морти кто виноват в том или ином проишествии.

Для начала было решено пронумеровать всех Риков по уменьшению важности от $$$1$$$ до $$$n$$$, а Морти — по увеличению неважности от $$$1$$$ до $$$m$$$. Иерархию обитателей цитадели решили изобразить в виде подвешенного дерева, при чем

• в дереве ровно $$$n$$$ внутренних вершин и $$$m$$$ листьев, и все листья дерева находятся на одной глубине;
• все внутренние вершины заняты Риками, а все листья заняты Морти (разумеется, все Морти должны находиться в самом низу иерархии);
• номера всех Риков на любом уровне меньше, чем номера Риков на следующих уровнях (в частности, в корне дерева всегда находится Верховный Рик под номером $$$1$$$);
• на каждом уровне Рики пронумерованы по возрастанию слева-направо;
• у каждого Рика до предпоследнего слоя есть хотя бы два непосредственных подчиненных.

Рики, разумеется, быстро справились с построением такой иерархии, а вот Морти в панике выстроились на нижнем уровне в каком-то случайном порядке. Посмотрев на этот хаос, Рики решили, что раз они все равно не очень любят правила, то правило про упорядоченность Риков на каждом уровне можно отменить, а вот Морти на нижнем уровне надо упорядочить по возрастанию номеров слева-направо.

Для этого каждому Рику было разрешено поменять своих непосредственных подчиненных местами произвольным образом. При этом менять множество своих подчиенных, то есть брать новых или отдавать старых кому-то еще, а также перемещаться на другой уровень иерархии, запрещено. Получится ли у Риков таким образом упорядочить всех Морти по возрастанию? Ниже приведен пример возможного решения:

Изначальная иерархия и действия, необходимые для упорядочивания Морти.

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

В первой строке через пробел перечислены два целых числа $$$n$$$ и $$$m$$$ — количество Риков и Морти в Цитадели, соответственно ($$$2 \leqslant n, m \leqslant 10^5$$$).

Во второй строке через пробел перечислены $$$m$$$ различных целых чисел $$$a_i$$$ — номера Морти в порядке их следования в изначально построившейся иерархии слева-направо ($$$1 \leqslant a_i \leqslant m$$$).

В следующей строке через пробел перечислены числа $$$p_2$$$, ..., $$$p_n$$$ — номера непоредственных начальников Риков с номерами от $$$2$$$ до $$$n$$$ ($$$1 \leqslant p_i < i$$$).

В следующей строке, аналогично, перечислены $$$m$$$ целых чисел $$$q_1$$$, ..., $$$q_m$$$ — номера непосредственных начальников всех Морти, в порядке, в котором они следуют в исходной иерархии ($$$1 \leqslant q_i \leqslant n$$$). Обратите внимание, что $$$q_1$$$ — номер начальника Морти с номером $$$a_1$$$, а не с номером $$$1$$$.

Гарантируется, что структура иерархии соответствует заданным в условии ограничениям.

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

В единственной строке выведите «YES» (без кавычек), если Рики, меняя местами непосредственных подчиненных, могут упорядочить всех Морти по возрастанию номеров, и «NO» иначе.

ПримерыВходные данные

4 4
1 3 2 4
1 1 1
2 2 3 4

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

NO

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

8 10
10 9 8 3 4 5 7 6 1 2
1 1 2 2 3 3 3
4 5 5 6 6 7 7 7 8 8

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

YES