a269. TOI 2020/12 潛力組：空中鋼索

題目描述

山區有 N 個基地，第 i 個基地的高度為 hi。兩個基地之間若有鋼索，只能從較高的基地滑向較低的基地；高度相同時不能通行。每對基地之間最多有一條鋼索。

你要從基地 1 前往基地 N，並希望使用的鋼索條數最多，也就是途中轉乘次數最多。請計算具有最多轉乘次數的路線共有幾條。路線由依序經過的基地決定；若無法抵達，答案為 0。

輸入格式

第一行有 N、M；第二行有 N 個高度。接著 M 行各有 a、b，表示兩個基地間有鋼索。

• 2 ≤ N ≤ 10000
• 1 ≤ M ≤ min(N(N−1)/2,100000)
• 0 ≤ hi ≤ 1000000000
• 1 ≤ a、b ≤ N，a ≠ b；沒有重複鋼索。

輸出格式

輸出符合條件的路線總數。須輸出完整整數，不取餘數。

來源

TOI 2020 年 12 月潛力組〈空中鋼索〉。題意以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202012/Zipline.pdf