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

样例输入 #1

3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

样例输出 #1

NO

样例 #2

样例输入 #2

3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

样例输出 #2

YES

样例 #3

样例输入 #3

2
galileo galilei
nicolaus copernicus
2 1

样例输出 #3

YES

样例 #4

样例输入 #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

样例输入 #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.