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: $\forall i, j(i < j) : h_{p_{i}} < h_{p_{j}}$.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — 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 2n strings will be distinct.

The next line contains n distinct integers: p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n).


-----Output-----

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


-----Examples-----
Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

Output
NO

Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

Output
YES

Input
2
galileo galilei
nicolaus copernicus
2 1

Output
YES

Input
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

Output
NO

Input
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

Output
YES



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Contest 270 Problem C

Author  : chaotic_iak
Language: Python 3.3.4
"""

def main():
    n, = read()
    names = []
    for i in range(n): names.extend([(x,i+1) for x in read(1)])
    names.sort()
    p = read()
    i = 0
    j = 0
    while i < n and j < 2*n:
        if names[j][1] == p[i]:
            i += 1
        j += 1
    if i == n:
        print("YES")
    else:
        print("NO")

################################### NON-SOLUTION STUFF BELOW

def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

n = int(input())
l = [input().split() for i in range(n)]
p = [int(x)-1 for x in input().split()]

cur = ""
poss = True
for i in range(n):
    per = l[p[i]]
    if per[0] > cur:
        if per[1] > cur:
            cur = min(per[0],per[1])
        else:
            cur = per[0]
    else:
        if per[1] > cur:
            cur = per[1]
        else:
            poss = False
            break
print("YES" if poss else "NO")


from sys import *
n = int(input())
names = []
for i in range(n):
    names.append(input().split())
p = [names[x - 1] for x in list(map(int, input().split()))]
curr_handle = min(p[0][0], p[0][1])
for i in range(1, n):
    if curr_handle > p[i][0] and curr_handle > p[i][1]:
        print("NO")
        return
    else:
        min_curr = min(p[i][0], p[i][1])
        curr_handle = min_curr if curr_handle <= min_curr else max(p[i][0], p[i][1])
print("YES")


import sys

n = int(input())

name = []
for i in range(n):
    s = input().split()
    name.append(s)

p = list(map(int, input().split()))
for i in range(n):
    p[i] -= 1

new = [0] * n
for i in range(n):
    new[i]= name[p[i]]


now = min(new[0][0], new[0][1])

for i in range(1, n):
    tmp1 = min(new[i][0], new[i][1])
    tmp2 = max(new[i][0], new[i][1])

    if now < tmp1:
        now = tmp1
    elif now < tmp2:
        now = tmp2
    else:
        print("NO")
        return

print("YES")


n = int(input())
name = [""] * n
surname = [""] * n
for i in range(n):
    name[i], surname[i] = input().split()

a = list(map(int, input().split()))
new_name = []
new_surname = []
for i in a:
    new_name.append(name[i - 1])
    new_surname.append(surname[i - 1])

dp = [[False] * 2 for i in range(n)]
dp[0][0] = True
dp[0][1] = True

for i in range(n - 1):
    if dp[i][0]:
        if new_name[i] < new_name[i + 1]:
            dp[i + 1][0] = True
        if new_name[i] < new_surname[i + 1]:
            dp[i + 1][1] = True
    if dp[i][1]:
        if new_surname[i] < new_name[i + 1]:
            dp[i + 1][0] = True
        if new_surname[i] < new_surname[i + 1]:
            dp[i + 1][1] = True

if dp[n - 1][0] or dp[n - 1][1]:
    print("YES")
else:
    print("NO")

n = int(input())
tmp = [input().split() for _ in range(n)]
p = list(map(int, input().split()))
l = [None] * n
for i, v in enumerate(p):
    l[i] = tmp[v - 1]
l[0] = min(l[0])
for i in range(1, n):
    if min(l[i]) > l[i - 1]:
        l[i] = min(l[i])
    elif max(l[i]) > l[i - 1]:
        l[i] = max(l[i])
    else:
        print('NO')
        break
else:
    print('YES')

n = int(input())
name = ['' for i in range(n)]
sname = ['' for i in range(n)]
for i in range(n):
	name[i], sname[i] = input().split()
p = list(map(int, input().split()))
for i in range(n):
	p[i] -= 1
nm = [False for i in range(n)]
snm = [False for i in range(n)]
nm[0] = snm[0] = True
for i in range(1, n):
	if nm[i-1]:
		if name[p[i]] > name[p[i-1]]:
			nm[i] = True
		if sname[p[i]] > name[p[i-1]]:
			snm[i] = True
	if snm[i-1]:
		if name[p[i]] > sname[p[i-1]]:
			nm[i] = True
		if sname[p[i]] > sname[p[i-1]]:
			snm[i] = True
print("YES" if snm[-1] or nm[-1] else "NO")

# 472 C

a = int(input())
l = []
l1 = []
for i in range(a):
    l.append('')
for i in range(a):
    lol = input().split()
    l1.append([lol[0],lol[1]])
l2 = input().split()

for i in range(a):
    l[i] = l1[int(l2[i])-1]
m = ''
work = "YES"
for i in range(a):
    if min(l[i]) >= m:
        m = min(l[i])
    elif max(l[i]) >= m:
        m = max(l[i])
    else:
        work = "NO"
        break

print(work)


n = int(input())
l = []
for i in range(n):
    k, h = input().split()
    l.append([k, i + 1])
    l.append([h, i + 1])
a = list(map(int, input().split()))
l.sort()
cur = 0
ind = 0
ans = 'YES'
while (ind < 2 * n) and (cur < n):
    while l[ind][1] != a[cur]:
        ind += 1
        if ind >= 2 * n:
            ans = 'NO'
            break
    cur += 1
print(ans)

#input
n=int(input())
namelist=[]
for i in range(n):
	namelist.append([str(x) for x in input().split()])
plist=[int(x) for x in input().split()]



#variables
limit=min(namelist[plist[0]-1])



#main
for i in range(n-1):
	if limit<min(namelist[plist[i+1]-1]):
		limit=min(namelist[plist[i+1]-1])
	elif limit<max(namelist[plist[i+1]-1]):
		limit=max(namelist[plist[i+1]-1])
	else:
		print('NO')
		quit()

print('YES')

'''
Created on Sep 28, 2014

@author: Ismael
'''

def selectLeastGreater(p,prec):
    fn = p[0]
    ln = p[1]
    if(fn >= prec and fn <= ln):
        return fn
    elif(ln >= prec and ln <= fn):
        return ln
    elif(fn >= prec):
        return fn
    elif(ln >= prec):
        return ln
    else:
        return ""

n = int(input())
names = []
for _ in range(n):
    fn,ln = input().split()
    names.append((fn,ln))
A = list(map(int,input().split()))
#print(names)
#print(A)
names2 = []
for i in A:
    names2.append(names[i-1])
#print(names2)
prec = ""
YES = True
for i in range(n):
    new = selectLeastGreater(names2[i],prec)
    if(len(new) == 0):
        print("NO")
        YES = False
        break
    else:
        prec = new
if(YES):
    print("YES")

n = int(input())
names = []
for i in range(n):
    names.append(input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
p = [0]*n
for i in range(n):
    p[a[i]] = i
ans = "YES"
choice = 0
for i in range(n-1):
    if choice == 0:
        if min(names[a[i]][0], names[a[i]][1]) > max(names[a[i+1]][0], names[a[i+1]][1]):
            ans = "NO"
        else:
            if min(names[a[i]][0], names[a[i]][1]) > names[a[i+1]][0]:
                choice = 2
            elif min(names[a[i]][0], names[a[i]][1]) > names[a[i+1]][1]:
                choice = 1
    elif choice == 1:
        if names[a[i]][0] > max(names[a[i+1]][0], names[a[i+1]][1]):
            ans = "NO"
        else:
            if names[a[i]][0] > names[a[i+1]][0]:
                choice = 2
            elif names[a[i]][0] > names[a[i+1]][1]:
                choice = 1
            else:
                choice = 0
    elif choice == 2:
        if names[a[i]][1] > max(names[a[i+1]][0], names[a[i+1]][1]):
            ans = "NO"
        else:
            if names[a[i]][1] > names[a[i+1]][0]:
                choice = 2
            elif names[a[i]][1] > names[a[i+1]][1]:
                choice = 1
            else:
                choice = 0
            
print(ans)

n=int(input())
names=[]
sortnames=[]
result = "YES"
for i in range(n):
    names.append(input().split(' '))
    sortnames.append('')
k = input().split(' ')
for i in range(n):
    k[i] = int(k[i])
    sortnames[i] = names[k[i]-1]
    sortnames[i].sort()
sortnames[0] = sortnames[0][0]
for i in range(n-1):
    if sortnames[i] < sortnames[i+1][0]:
        sortnames[i+1] = sortnames[i+1][0]
    else:
        if sortnames[i] < sortnames[i+1][1]:
            sortnames[i+1] = sortnames[i+1][1]
        else:
            result = "NO"
            break
print(result)


false = False
curr = []
names = int(input())
ppl = [input().split(' ') for i in range(names)]
order = list(map(str, input().split(' ')))
for i in range(names):
    if i == 0:
        curr.append(min(ppl[int(order[i])-1]))
    else:
        a = ppl[int(order[i])-1][0]
        b = ppl[int(order[i])-1][1]
        if curr[-1] <= min(a, b):
            curr.append(min(a, b))
        elif curr[-1] <= max(a, b):
            curr.append(max(a, b))
        else:
            false = True
if false:
    print("NO")
else:
    print("YES")


n = int(input())
a = ['']*n
b = ['']*n
c = ['']*n

for i in range(n):
    s = input()
    k = s.find(' ')
    a[i] = s[:k]
    b[i] = s[k+1:]
k = 0
p = list(map(int, input().split()))
for j in p:
    i = j - 1
    if k == 0:
        c[k] = min(a[i],b[i])
        k+=1
    else:
        if a[i] > c[k-1] and not (b[i] > c[k-1] and b[i] < a[i]):
            c[k] = a[i]
        elif b[i] > c[k-1]:
            c[k] = b[i]
        else:
            print('NO')
            break
        k+=1
else:
    print('YES')

n = int(input())
f = [input().split() for i in range(n)]
m=[False, False]
sl = list(map(int, input().split()))
if n==1:
    print("YES")
else:
    if f[sl[0]-1][0]<=f[sl[1]-1][0] or f[sl[0]-1][1]<=f[sl[1]-1][0]:
        m[0]=True
    if f[sl[0]-1][0]<=f[sl[1]-1][1] or f[sl[0]-1][1]<=f[sl[1]-1][1]:
        m[1]=True
    a, b = False, False
    for i in range(1, n-1):
        if (m[0] and (f[sl[i]-1][0]<=f[sl[i+1]-1][0])) or (m[1] and (f[sl[i]-1][1]<=f[sl[i+1]-1][0])):
            a = True 
        else:
            a = False
        if (m[0] and (f[sl[i]-1][0]<=f[sl[i+1]-1][1])) or (m[1] and (f[sl[i]-1][1]<=f[sl[i+1]-1][1])):
            b = True
        else:
            b = False
        m[0], m[1] = a, b   
    if (not m[0]) and (not m[1]):
        print("NO")
    else:
        print("YES")

#!/usr/bin/env python3

person_count = int(input())
person_list = [input().split(" ") for _ in range(person_count)]
order = [int(x) - 1 for x in input().split(" ")]
string = ""
for number in order:
    if string <= person_list[number][0] and string <= person_list[number][1]:
        string = min(person_list[number])
    elif string <= person_list[number][0]:
        string = person_list[number][0]
    elif string <= person_list[number][1]:
        string = person_list[number][1]
    else:
        print("NO")
        break
else:
    print("YES")


n = int(input())
names = []
for i in range(n):
    names.append(input().split())
p = [int(i) - 1 for i in input().split()]
last = min(names[p[0]][0], names[p[0]][1])
for i in range(1, n):
    a = names[p[i]]
    v = []
    if last < a[0] :
        v.append(a[0])
    if last < a[1]:
        v.append(a[1])
    if len(v) == 0:
        print('NO')
        break
    else:
        last = min(v)
else:
    print('YES')


n = int(input())
s = []
for i in range(n):
    s.append(input().split())
    if s[i][0] > s[i][1]:
        s[i][0], s[i][1] = s[i][1], s[i][0];
x = [int(i) - 1 for i in input().split()]

tag = False
#for item in s:
#    print(item)
for i in range(1, n):
    if s[x[i-1]][0] >= s[x[i]][1]:
        print('NO')
        tag = True
        break
    if s[x[i-1]][0] >= s[x[i]][0]:
        s[x[i]][0] = s[x[i]][1]
    #print(s[i][0])
if tag == False:
    print('YES')


import sys 
import queue

#file = open("in.txt", "r")
#sys.stdin = file

line = sys.stdin.readline()

n = int(line)

first = ["" for x in range(n)]
second = ["" for x in range(n)]

for i in range(0, n):
    line = sys.stdin.readline().split()
    first[i] = line[0]
    second[i] = line[1]

permutation = [int(x) for x in sys.stdin.readline().split()]

p = permutation[0]-1
last = min(first[p], second[p])


can = True

for i in range(1, n):
    p = permutation[i]-1
    if last < min(first[p], second[p]):
        last = min(first[p], second[p])
    elif last < max(first[p], second[p]):
        last = max(first[p], second[p])
    else:
        can = False

if can:
    print("YES")
else:
    print("NO")






n = int(input())
i = 1
l = []
while i <= n:
    l.append(input().split())
    i+=1
a = [int(p) for p in input().split()]
#print(n,l,a)
i = 1

def t(l,a):
    w = min(l[a[0]-1][0], l[a[0]-1][1])
    del a[0]
    for p in a:
        k = min(l[p-1][0],l[p-1][1])
        if k > w:
            w = k
        elif max(l[p-1][0],l[p-1][1]) > w:
            w = max(l[p-1][0],l[p-1][1])
        else:
            return 'NO'
    return 'YES'
print(t(l,a))

n=int(input())
l=[None]*n
i=0
while i<n:
    l[i]=input().split()
    i+=1
z=[int(px) for px in input().split()]
x=1
y=True
a=min(l[z[0]-1])
while x<n:
    u=l[z[x]-1][0]
    v=l[z[x]-1][1]
    if(u<a and v<a):
        y=False
        break
    elif(u>a and v>a):
        a=min(u,v)
    else:
        a=max(u,v)
    x+=1    
if(y):
    print("YES")
else:
    print("NO")

n=int(input())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(n):
    a[i],b[i]=input().split()
d=list(map(int,input().split()))


answer="YES"
c[0]=min(a[d[0]-1],b[d[0]-1])
for i in range(1,n):
    if c[i-1]<min(a[d[i]-1],b[d[i]-1]):
        c[i]=min(a[d[i]-1],b[d[i]-1])
    elif c[i-1]<max(a[d[i]-1],b[d[i]-1]):
        c[i]=max(a[d[i]-1],b[d[i]-1])
    else:
        answer="NO"
        break
print(answer)

def greater(a,b):
    n = [b,a]
    m = sorted(n)
    if n[0] == m[0] :
        return True
    else :
        return False

n = int(input())
name = []
for i in range(n) :
    name.append(sorted(list(input().split())))
p = list(map(int,input().split()))
r = 'YES'
result = [name[p[0]-1][0]]
for i in range(1,n) :
    j = p[i] - 1
    if greater(name[j][0],result[i-1]) :
        result.append(name[j][0])
    elif greater(name[j][1], result[i-1]) :
        result.append(name[j][1])
    else :
        r = 'NO'
        break
print(r)