CSES 3357 - Fixed Length Walk Queries

給你一張有 \(n\) 個節點與 \(m\) 條邊的無向圖。這張圖是簡單圖，而且是連通的。

你從某個指定的節點出發，每一回合都必須沿著一條邊移動到另一個節點。

你的任務是回答 \(q\) 筆形式如下的詢問：「能不能從節點 \(a\) 出發，在恰好 \(x\) 個回合之後停在節點 \(b\)？」

輸入格式

第一行有三個整數 \(n\)、\(m\) 與 \(q\)：節點數量、邊數量與詢問數量。節點編號為 \(1,2,\dots,n\)。

接下來有 \(m\) 行描述邊。每行有兩個整數 \(a\) 與 \(b\)：節點 \(a\) 與 \(b\) 之間有一條邊。

最後有 \(q\) 行，每行描述一筆詢問。每行有三個整數 \(a\)、\(b\) 與 \(x\)。

輸出格式

對每筆詢問，各自輸出一行答案（YES 或 NO）。

範例輸入 1

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

範例輸出 1

YES
NO
YES
NO
YES
YES

說明：

• 在第 1 筆詢問中，一條可行的路線是 \(1 \rightarrow 3 \rightarrow 2\)。
• 在第 3 筆詢問中，一條可行的路線是 \(1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4\)。
• 在第 6 筆詢問中，一條可行的路線是 \(3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4\)。

限制

• \(2 \le n \le 2500\)
• \(1 \le m \le 5000\)
• \(1 \le q \le 10^5\)
• \(0 \le x \le 10^9\)

題目來源

CSES - Fixed Length Walk Queries

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。