Олимпиадный тренинг

Задача . C. Уроки дизайна задач: недетеминированность


Задача

Темы: *1400 жадные алгоритмы

Один из способов придумать новую задачу — взять существующую задачу и добавить в нее некоторую недетерминированность. Например, самая сложная задача с Topcoder SRM 595, Constellation, является вероятностной версией выпуклой оболочки.

Попробуем придумать новую задачу описанным способом. Для начала возьмем следующую задачу. Заданы описания n людей, отсортируйте их в лексикографическом порядке по именам. Это обычная задача на сортировку, но ее можно сделать интереснее, добавив случайный элемент. Заданы описания n людей, каждый человек выбирает в качестве хендла либо свое имя, либо фамилию. Может ли лексикографический порядок хендлов в точности совпадать с перестановкой p?

Более формально, если мы обозначим хендл i-го человека как hi, то должно выполняться следующее условие: .

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество людей.

В каждой из следующих n строк записано по две строки. В i-й из них записаны строки fi и si (1 ≤ |fi|, |si| ≤ 50) — имя и фамилия i-го человека. Каждая строка состоит исключительно из строчных букв английского алфавита. Все заданные 2n строк будут различны.

В следующей строке записано n различных целых чисел: p1, p2, ..., pn (1 ≤ pi ≤ n).

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

Если это возможно, выведите «YES», в противном случае выведите «NO».

Примечание

В примерах номер 1 и 2 у нас есть 3 человека: tourist, Petr и я (cgy4ever). Как вы видите, вне зависимости от выбранного хендла, сначала должен идти я, затем — tourist и последним — Petr.

В примере номер 3 все будет в порядке, если Copernicus возьмет в качестве хендла «copernicus».


Примеры
№Входные данныеВыходные данные
1 
3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3
 
NO
2 
3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2
 
YES
3 
2
galileo galilei
nicolaus copernicus
2 1
 
YES
4 
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
1 2 3 4 5 6 7 8 9 10
 
NO
5 
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
2 4 9 6 5 7 1 3 8 10
 
YES

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++4
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет