TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (25/25)

Submission's AC Ratio

56.1% (37/66)

Description

大學的課程是多采多姿的。

每個人可以選修想要學習的課程,可說是讓每個人適性發展。

但是因為預備知識以及預先需要的技術的關係,所以有一些課程需要先學習某些課程才能夠選修,這則稱做『擋修』。

現在你有 n 種想要學習的課程,並將它從 1 編號到 n,並且排成一個學習序列,裡面的數字只會有1~n各一個。

但是你突然發現有 m 個『擋修』關係,這可能會讓你原先的學習計畫不能夠實行。

到底你能不能按照你原先的計畫實行呢?

Input Format

本題有多筆測試資料,以EOF作為結束:

每筆資料的第一行有兩個數字 n, m,代表你有 n 種想要學習的課程以及 m 個『擋修』關係
(0 < n <= 1,000, 0 < m <=10,000,000)
接下來有 m 行,每行有兩個數字 ai, bi,代表你需要先學習編號ai的課程才能學習編號bi的課程

接下來有一行,裡面包含 n 個數字,依序是你的學習序列

Output Format

請對於每筆資料輸出一行,若能夠實行請輸出"YES"(不含雙引號),否則輸出"NO"(不含雙引號)

Sample Input

5 6
1 3
1 4
3 5
5 2
4 2
1 2
1 3 4 5 2
5 6
1 3
1 4
3 5
5 2
4 2
1 2
1 2 4 5 3

Sample Output

YES
NO

Hints

Problem Source

原TIOJ1456 / 建中校內培訓第三次模擬考試。
Problem Setter:hallogameboy、peter50216
03'-04' ACM CR of Russia PC

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 10000 65536
1 10000 65536
2 10000 65536
3 10000 65536
4 10000 65536
5 10000 65536
6 10000 65536
7 10000 65536
8 10000 65536
9 10000 65536
10 10000 65536