← 返回题目列表

Codeforces · 472/C

C. 设计教程:使其具有非确定性

中文机器翻译题面 查看原题

制定新任务的一种方法是使其具有非确定性或概率性。例如,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

3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

输出 #1

NO

输入 #2

3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

输出 #2

YES

输入 #3

2
galileo galilei
nicolaus copernicus
2 1

输出 #3

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

输出#4

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

输出 #5

YES

注意

在示例 1 和 2 中,我们有 3 个人:游客、Petr 和我 (cgy4ever)。你可以看到,无论选择什么手柄,我一定是第一个,然后游客和 Petr 一定是最后一个。

在示例3中,如果哥白尼使用“copernicus”作为他的句柄,那么一切都会好起来的。