制定新任务的一种方法是使其具有非确定性或概率性。例如,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”作为他的句柄,那么一切都会好起来的。