CSES 1705 - Forbidden Cities

有 \(n\) 座城市與 \(m\) 條連接它們的道路。Kaaleppi 目前在城市 \(a\)，想要前往城市 \(b\)。

不過有個問題：Kaaleppi 最近在城市 \(c\) 搶了一家銀行，所以不能進入那座城市，否則會被當地警察逮住。你的任務是判斷是否存在一條從城市 \(a\) 到城市 \(b\)、而且不會經過城市 \(c\) 的路線。

作為額外的挑戰，你必須處理 \(q\) 筆詢問，每筆的 \(a\)、\(b\) 與 \(c\) 都可能不同。

輸入格式

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

接下來有 \(m\) 行描述道路。每行有兩個整數 \(a\) 與 \(b\)：城市 \(a\) 與 \(b\) 之間有一條道路。每條道路都是雙向的。

最後有 \(q\) 行描述詢問。每行有三個整數 \(a\)、\(b\) 與 \(c\)：是否存在一條從城市 \(a\) 到城市 \(b\)、而且不經過城市 \(c\) 的路線？

你可以假設任兩座城市之間都有路線相通。

輸出格式

對每筆詢問，若存在這樣的路線就輸出 YES，否則輸出 NO。

範例輸入 1

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

範例輸出 1

YES
NO
YES

限制

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le q \le 10^5\)
• \(1 \le a,b,c \le n\)

題目來源

CSES - Forbidden Cities

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