雄中湖

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

雄中湖有許多小島被標示成不同的編號(\(1, 2, 3...n\)),而不同的小島之間需要靠橋來連接。
今天宇晨跟大黑在玩捉迷藏,一開始他們會分別位在不同的小島。
而由於大黑非常的懶,牠在遊戲開始的瞬間就會開始睡覺,待在原地不動。
請問宇晨有沒有辦法透過橋走到大黑的小島?

Input

第一行有三個自然數\(n, m, q\),表小島數量和橋的數量,以及要查詢的次數。
接下來有\(m\)行,每行有\(i, j\)兩自然數,表示\(i\)和\(j\)之間有一座橋(島嶼\(x\)與\(y\)之間的橋樑只會出現一次,也就是每次輸入的橋都是不一樣的)。
再來有\(q\)行,每行有兩自然數\(a, b\),分別代表宇晨和大黑一開始的位置。

Output

對於每次查詢,請輸出一行。如果宇晨不能走到大黑的島嶼,請輸出"No",反之則輸出"Yes" (不包含引號)。

Constraints

第 \(1\) 組測資, \(n\leq10\), \(m=1\), \(q=1\)。 \((20\text{%})\)

第 \(2\) 組測資, \(n\leq10\), \(q=1\)。 \((30\text{%})\)

第 \(3\) 組測資, \(n\leq10^3\), \(q\leq10^4\)。 \((30\text{%})\)

第 \(4\) 組測資, \(n\leq10^5\), \(q\leq10^5\)。 \((20\text{%})\)

對於所有測資,\(n > 1\), \(m\leq min(\frac{n(n-1)}{2}, 4*10^4)\)。

Sample Input
6 3 3
1 2
2 4
3 5
1 4
2 3
1 6
Sample Output
Yes
No
No

Comments

There are no comments at the moment.