請注意,這題測資範圍與上題並不相同!
鹽亞倫終於將伺服器修好了!但是,他馬上遇到另一個麻煩。
由於伺服器的安全憑證過期了,因此要連線到網站時 Chrome 都會出現這個畫面:
如果要解決這個問題,鹽亞倫必須替伺服器申請一個安全憑證才行。在當前的網際網路當中,安全憑證是透過所謂的信任機制進行認證的。
什麼是信任機制呢?在網路當中,有一些機構稱之為數位憑證認證機構(Certificate Authority,簡稱CA),這一些 CA會為每個可信任的用戶,來發放一個「憑證」,目的是證明這個憑證中列出的用戶皆是安全可信任的,絕對不是一些來路不明的怪怪網站。
但是你會發現,如果駭客團體自己註冊了一家CA,替一些非法網站進行加密驗證,該怎麼辦呢?因此,CA 之間存在著所謂的信任關係。
講白一點,就是一個A機構要被另一個B機構來認證是否安全,而B機構也要被更大規模的C機構認證......一直重複下去。而如果使用者相信C機構是安全可靠的,他也會信任B機構以及被B機構認證的A機構是安全可靠的。
也因此若當兩台電腦的CA機構沒有彼此信任,那麼chrome就會出現不安全網路的錯誤訊息了。
顯然的,鹽亞倫只會搞破壞,是不會看不懂以上關係的。遲遲無法決定到底要向哪張CA申請安全憑證的他,只好拿著一張總共有n家CA機構以及m條信任關係的列表來找你,希望你可以幫他判斷兩家CA之間是否彼此信任。
第一行有三個整數$n \, m\, q$,代表n家CA機構、m條信任關係,以及鹽亞倫總共會問你q次問題
接下來的m行每行有兩個整數 $X_a\,X_b$,代表這兩家公司彼此信任
接下來的q行每行有兩個整數 $Y_a\,Y_b$,代表鹽亞倫問你這兩家公司是否透過信任鏈彼此信任。
測資範圍:
$1 \le n, m \le 2000000$
$1 \le X_a,\ X_b,\ Y_a,\ Y_b$ 且 $X_a,\ X_b,\ Y_a,\ Y_b \le n$
不保證 $X_a$ 不等於 $X_b$且不會有重複的信任關係
對於每次詢問,
如果彼此信任,輸出YES
並換行
如果彼此不信任,輸出yes
並換行
No. | Testdata Range | Score |
---|