a355. TOI 2019/12 潛力組：旅行

題目描述

小軒想規劃一趟旅行。他所在的星球有許多國家，國家之間只能搭乘飛機往來，但只有指定的航班可以使用，並非任意兩個國家都能互相到達。

給定各航班的出發地與目的地，請回答每筆查詢：能否從國家 A 出發，經由搭乘飛機到達國家 B？旅途中可以在其他國家轉機。航班依所列的出發地飛往目的地，不能直接視為雙向航班。

輸入格式

第一行包含三個整數 N、M、Q，分別代表國家數、航班數與查詢數。

• 2 ≤ N ≤ 200
• 1 ≤ M ≤ N(N − 1)
• 1 ≤ Q ≤ 20000
• 國家編號為 0 至 N − 1

接著 M 行，每行包含兩個國家編號，依序表示一個航班的出發地與目的地。

再接著 Q 行，每行包含兩個國家編號 A、B，表示查詢是否能從 A 國經由搭乘飛機到達 B 國。

原題分組限制：30 分的資料滿足 2 ≤ N ≤ 5、1 ≤ M ≤ 20、1 ≤ Q ≤ 10；其餘 70 分無額外限制。

輸出格式

對每筆查詢輸出一行。如果可以從 A 國經由搭乘飛機到達 B 國，輸出 YES；否則輸出 NO。

來源

TOI 2019 年 12 月練習賽潛力組〈旅行（Trip）〉。本敘述依官方原題 PDF 重新整理。

原題連結：https://tpmso.org/toi/wp-content/uploads/question/201912/A3-Trip.pdf

題目鏡像：https://zerojudge.tw/ShowProblem?problemid=e792