Design Tutorial: Make It Nondeterministic

题意翻译

### 题目描述 很多场合，名字是按姓的字典序排序的，但有的时候东方人和西方人姓名的顺序不一样，不知道哪个是姓，哪个是名，于是问题来了。给你n个人的姓名，每个姓名由两个字符串构成，有些姓在前，有的姓在后。现在给出这些人的排序，问这样的序列是否可能是这些名字的字典序排序。 ### 输入格式 输入n 然后n行每行输入两个字符串。 最后一行输入一种n个数字的排列。 ### 输出格式 如果可能是排列的顺序就输出YES， 否则输出NO。 ### 数据规模和约定 1<=n<=10^5 1<=字符串长度<=50。 字符串一样时，顺序可任意。

题目描述

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: .

输入输出格式

输入格式

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: .

输出格式

If it is possible, output "YES", otherwise output "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

说明

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.