472C.md (2591B)
1 Source: https://codeforces.com/problemset/problem/472/C 2 3 C. Design Tutorial: Make It Nondeterministic 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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*? 24 25 More formally, if we denote the handle of the *i*-th person as *h**i*, then the following condition must hold: . 26 27 Input 28 29 The first line contains an integer *n* (1 ≤ *n* ≤ 105) — the number of people. 30 31 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. 32 33 The next line contains *n* distinct integers: *p*1, *p*2, ..., *p**n* (1 ≤ *p**i* ≤ *n*). 34 35 Output 36 37 If it is possible, output "YES", otherwise output "NO". 38 39 Examples 40 41 Input 42 43 ``` 44 3 45 gennady korotkevich 46 petr mitrichev 47 gaoyuan chen 48 1 2 3 49 ``` 50 51 Output 52 53 ``` 54 NO 55 ``` 56 57 Input 58 59 ``` 60 3 61 gennady korotkevich 62 petr mitrichev 63 gaoyuan chen 64 3 1 2 65 ``` 66 67 Output 68 69 ``` 70 YES 71 ``` 72 73 Input 74 75 ``` 76 2 77 galileo galilei 78 nicolaus copernicus 79 2 1 80 ``` 81 82 Output 83 84 ``` 85 YES 86 ``` 87 88 Input 89 90 ``` 91 10 92 rean schwarzer 93 fei claussell 94 alisa reinford 95 eliot craig 96 laura arseid 97 jusis albarea 98 machias regnitz 99 sara valestin 100 emma millstein 101 gaius worzel 102 1 2 3 4 5 6 7 8 9 10 103 ``` 104 105 Output 106 107 ``` 108 NO 109 ``` 110 111 Input 112 113 ``` 114 10 115 rean schwarzer 116 fei claussell 117 alisa reinford 118 eliot craig 119 laura arseid 120 jusis albarea 121 machias regnitz 122 sara valestin 123 emma millstein 124 gaius worzel 125 2 4 9 6 5 7 1 3 8 10 126 ``` 127 128 Output 129 130 ``` 131 YES 132 ``` 133 134 Note 135 136 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. 137 138 In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.