TopCoder

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

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

32.0% (16/50)

Description

  第501統合戦闘航空団有個非常奇怪的位階制度,每個人的階級章上都會有一個數字。

  每個人最多只能有兩個部屬,一個部屬的數字會比自己大或是跟自己一樣大,而他的部屬也必須要遵守這個條件(比最上面的那個人大),而另外一個部屬則是要比他小,想當然爾,其部屬也必須要比最上面的那個人小。

  這個航空団非常重視階級制度,比較低階級的人絕對不可能是比較高階級的人的長官,而且每個人都只會有一個直屬長官。

  另外,所有人都會在同一個階級制度下,不會有人不在同一個系統中。

  現在你拿到了一張關係圖,雖然上面沒有誰是長官誰是部屬,但是卻有一對對的直屬長官-部屬關係的列表,你能否知道這有沒有可能就是他們完整的位階圖呢?

Input Format

本題只有一筆測試資料

第一行有兩個正整數n,m以空白隔開,代表有幾個人與幾對關係。(n<=1000 m<=n*(n-1)/2)

第二行有n個數字以空白隔開,代表第n個人階級章上的數字,保證這些數字都可以用32bit signed integer儲存

第三行開始有m行,每行有兩個數字a,b,代表a與b之間有關係(1<=a,b<=n)

Output Format

如果這張關係圖有可能是正確的位階圖

請輸出”YES” (不含雙引號)

反之請輸出”NO” (不含雙引號)

Sample Input

3 2
1 2 3
1 2
2 3

Sample Output

YES

Hints

Problem Source

原TIOJ1383 / 快樂暑假營第三次練習比賽。
Problem Setter:hallogameboy

Subtasks

No. Testdata Range Score
1 0~5 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1