TopCoder

ある雨の日に、私と君と。
音楽のみなそこに眠る、夢と想像の世界

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

25.8% (8/31)

Tags

Description

請注意,這題測資範圍與上題並不相同!


鹽亞倫終於將伺服器修好了!但是,他馬上遇到另一個麻煩。

由於伺服器的安全憑證過期了,因此要連線到網站時 Chrome 都會出現這個畫面:


如果要解決這個問題,鹽亞倫必須替伺服器申請一個安全憑證才行。在當前的網際網路當中,安全憑證是透過所謂的信任機制進行認證的。

什麼是信任機制呢?在網路當中,有一些機構稱之為數位憑證認證機構(Certificate Authority,簡稱CA),這一些 CA會為每個可信任的用戶,來發放一個「憑證」,目的是證明這個憑證中列出的用戶皆是安全可信任的,絕對不是一些來路不明的怪怪網站。

但是你會發現,如果駭客團體自己註冊了一家CA,替一些非法網站進行加密驗證,該怎麼辦呢?因此,CA 之間存在著所謂的信任關係。

講白一點,就是一個A機構要被另一個B機構來認證是否安全,而B機構也要被更大規模的C機構認證......一直重複下去。而如果使用者相信C機構是安全可靠的,他也會信任B機構以及被B機構認證的A機構是安全可靠的。

也因此若當兩台電腦的CA機構沒有彼此信任,那麼chrome就會出現不安全網路的錯誤訊息了。

顯然的,鹽亞倫只會搞破壞,是不會看不懂以上關係的。遲遲無法決定到底要向哪張CA申請安全憑證的他,只好拿著一張總共有n家CA機構以及m條信任關係的列表來找你,希望你可以幫他判斷兩家CA之間是否彼此信任。

Input Format

第一行有三個整數$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$且不會有重複的信任關係

Output Format

對於每次詢問,

如果彼此信任,輸出YES並換行

如果彼此不信任,輸出yes並換行

Sample Input 1

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

Sample Output 1

YES
yes
YES

Sample Input 2

8 9 7
2 2
3 8
6 3
2 7
1 6
4 4
7 2
4 5
1 1
6 2
8 8
7 2
10 3
6 9
5 5
7 8

Sample Output 2

yes
YES
YES
yes
yes
YES
yes

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 2000 250000 250000 65536
1 2000 250000 250000 65536
2 2000 250000 250000 65536
3 2000 250000 250000 65536
4 2000 250000 250000 65536
5 2000 250000 250000 65536
6 2000 250000 250000 65536
7 2000 250000 250000 65536
8 2000 250000 250000 65536
9 2000 250000 250000 65536
10 2000 250000 250000 65536
11 2000 250000 250000 65536
12 2000 250000 250000 65536
13 2000 250000 250000 65536
14 2000 250000 250000 65536
15 2000 250000 250000 65536
16 2000 250000 250000 65536
17 2000 250000 250000 65536
18 2000 250000 250000 65536
19 2000 250000 250000 65536