TopCoder

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

User's AC Ratio

100.0% (53/53)

Submission's AC Ratio

59.4% (95/160)

Tags

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 1

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 1

YES
NO

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11