姓名排序

题目描述

Y 同学正在整理一份 $N$ 个人的名单。由于文化差异，这 $N$ 个人的姓名有的习惯“姓在前名在后”，有的习惯“名在前姓在后”。

具体来说，对于第 $i$ 个人（$1 \le i \le N$），Y 同学已知他的两个字符串 $S_{i,1}$ 和 $S_{i,2}$，其中一个是姓，一个是名，但不确定具体的顺序。

现在，Y 同学得到了一份这些人的排列顺序 $P = \{p_1, p_2, \dots, p_N\}$。他想验证这个排列是否可能是一个合法的字典序排列。

也就是问：是否能为每个人 $p_i$ 从他的两个字符串 $\{S_{p_i, 1}, S_{p_i, 2}\}$ 中恰好选择一个作为“显示名称” $T_{p_i}$，使得最终生成的序列满足非递减的字典序关系：

注：字符串比较采用标准字典序（例如 "abc" < "abd"）。如果两个字符串完全相同，则视为满足 $\le$ 关系。

输入格式

第一行输入一个正整数 $N$，表示人数。

接下来的 $N$ 行，每行包含两个非空字符串，第 $i$ 行的两个字符串分别表示第 $i$ 个人的两个备选名字 $S_{i,1}$ 和 $S_{i,2}$。

最后一行输入 $N$ 个整数 $p_1, p_2, \dots, p_N$，表示给定的排列顺序。保证 $P$ 是 $1$ 到 $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

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N \le 10^5$
• 字符串仅包含小写英文字母。
• 每个字符串的长度不超过 $50$。