TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

87.0% (147/169)

Submission's AC Ratio

33.3% (257/772)

Tags

Description

有一天有n個人參加了一場宴會。這場宴會很特別,每個人都被標上了自己的號碼,第一個抵達的人被編為0號、第二個被編為1號、……、最後一個人編為n-1號。
當然,宴會少不了的是人與人之間的交流,尤其是兩人之間的握手。參加這場宴會的人們都很喜歡與別人握手,他們隨時會去找人握手,也有可能同樣的兩個人握手好幾次。更特別的是,有些人在無聊的時候會自己和自己握手。

有一個(邊緣)人默默地躲在角落,他沒有被列在這n個人當中,因為傳說中和他握到手的人都會遭遇不幸,沒有人願意讓他參加宴會。但是他覺得自己和自己握手實在是太蠢了,於是他決定做一件事:每一次兩個人握手時,他就那兩個人的編號記下來(如果是自己和自己握手,則他會把那個人的編號寫兩次)。一直到宴會結束,他總共紀錄了m次握手。

結束後,他想要分析宴會中每個人握手的情況,希望能分析出看有沒有人願意讓他參加下次的宴會。然而握手的次數實在太多了,讓他難以分析,因此他把他的紀錄交給你整理,等你整理完成後再問你q個問題,每一個問題都是「在這場宴會中編號為C的人和編號為D的人有沒有握過手」,以供他分析之用。
(注意, 雖然說C比D胖 C有可能等於D,因為他想知道這個人有沒有做了和自己握手這種愚蠢的行為。)

Input Format

第一行有三個正整數n, m, q,依序代表參加宴會的人數、握手的次數和詢問的次數。
接著有m行,每行有兩個非負整數Ai, Bi,代表編號為Ai的人和編號為Bi的人握了手。
接著有q行,每行有兩個非負整數Ci, Di,代表詢問編號為Ci的人和編號為Di的人有沒有握過手。
$n\leq 10^ 7; m, q\leq 10 ^ 6; A_i, B_i, C_i, D_i < n$。

子任務(測資) 額外限制 分數
1 (0~4) $n,m,q\leq 10^ 4$ 11
2 (5~9) $q\leq 100$ 13
3 (10~14) $m,q\leq 10^ 4$ 13
4 (15~19) 63

Output Format

請依照詢問的順序輸出q行,每行都代表一次詢問的答案。如果兩個人有握過手,輸出yes,否則輸出no

Sample Input 1

3 2 3
0 2
1 2
2 1
2 2
0 1

Sample Output 1

yes
no
no

Hints

事實證明,還是沒有人願意讓他參加宴會。

Problem Source

Problem set by Paupière
Description by Yihda Yol
建國中學105學年度校隊選拔:初試pC

Subtasks

No. Testdata Range Score
1 0~4 11
2 5~9 13
3 10~14 13
4 15~19 63

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1500 409600 262144 2
6 1500 409600 262144 2
7 1500 409600 262144 2
8 1500 409600 262144 2
9 1500 409600 262144 2
10 1000 204800 262144 3
11 1000 204800 262144 3
12 1000 204800 262144 3
13 1000 204800 262144 3
14 1000 204800 262144 3
15 4500 65536 262144 4
16 4500 65536 262144 4
17 4500 65536 262144 4
18 4500 65536 262144 4
19 4500 65536 262144 4