CF472C.Design Tutorial: Make It Nondeterministic

A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.

Let's try to make a new task. Firstly we will use the following task. There are n people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are n people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation p?

More formally, if we denote the handle of the i-th person as h__i, then the following condition must hold: .

构造新题目的一个方法是使其具有不确定性或概率性。例如，Topcoder SRM 595 的难题 “Constellation” 就是凸包问题的一个概率化版本。

我们来尝试构造一道新题目。首先考虑如下基础问题：有 $n$ 个人，按其姓名进行排序。这只是一个普通的排序问题，但我们可以加入不确定性元素使其更有趣：有 $n$ 个人，每个人将使用其名（first name）或姓（last name）之一作为昵称（handle）。是否存在一种选择方式，使得这些昵称的字典序恰好等于给定的排列 $p$？

更形式化地，若记第 $i$ 个人的昵称为 $h_i$，则需满足如下条件：

The first line contains an integer n (1 ≤ n ≤ 105) — the number of people.

The next n lines each contains two strings. The i-th line contains strings f__i and s__i (1 ≤ |f__i|, |s__i| ≤ 50) — the first name and last name of the i-th person. Each string consists only of lowercase English letters. All of the given 2_n_ strings will be distinct.

The next line contains n distinct integers: _p_1, _p_2, ..., p__n (1 ≤ p__i ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示人数。

接下来的 $n$ 行，每行包含两个字符串。第 $i$ 行包含字符串 $f_i$ 和 $s_i$（$1 \leq |f_i|, |s_i| \leq 50$）—— 分别表示第 $i$ 个人的名字和姓氏。每个字符串仅由小写英文字母组成。所有给出的 $2n$ 个字符串互不相同。

下一行包含 $n$ 个互不相同的整数：$p_1,\ p_2,\ \dots,\ p_n$（$1 \leq p_i \leq n$）。

If it is possible, output "YES", otherwise output "NO".

如果可能，输出“YES”，否则输出“NO”。

In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.

In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.

在示例 1 和 2 中，我们有 3 个人：tourist、Petr 和我（cgy4ever）。可以看出，无论选择哪个用户名，我都必须排在第一位，而 tourist 和 Petr 必须排在最后。

在示例 3 中，如果 Copernicus 使用 “copernicus” 作为他的用户名，则一切都会正常。