a796. F.房布的地圖
Tags :
Accepted rate : 107人/111人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-11-29 02:09

Content

  房布屠龍成功後,除了得到一大堆寶物(就像RPG遊戲打王會掉珍貴寶物),他還覺得神清氣爽,心情愉悅,如大夢初醒一般,雖然腦中仍然沒有畫面,但是他仍覺得他有個地方要回去。

  在他的黑畫面中尋找了甚久,房布對於他的歸宿仍然沒有感覺,彷彿所有先前的記憶都被蓋住了一樣。

  後來,他在整理那一大堆寶物的時候,發現那堆寶物除了K金的項鍊、三塊樂高積木、2013延平暑假快樂程設營家長同意書、無盡之刃、延平中學學生手冊、還有Dev-C++外,還有一項神奇的寶物上面寫著「神奇的房布的記憶」,房布迫不及待的把它打開,然而,除了一張神奇的地圖外什麼都沒有。

  「如果我跟著這張神奇的地圖的指引,我應該就能找回我神奇的記憶了吧。」房布想。

        那張神奇的地圖上標示著許多城市以及城市間的道路,而且這張神奇的地圖還有很多神奇的地方,首先,任兩條路都很神奇地不會相交,而且每條路總是連接著兩個神奇的城市,更神奇的是,任兩個城市之間最多只會有一條路連通兩者。

  但是房布完全不會看地圖,他希望聰明的你可以提供協助。

  房布他想知道地圖上的兩種資訊:

1.    某一個城市跟多少個城市有路可以直接連通(不經由其他城市)

2.    某兩城市間是否有一條路直接連通(不經由其他城市)

Input

  每個輸入檔僅含一組測試資料。

  第一行有一個正整數N,代表城市的數量,編號為1~N。

  第二行有一個正整數R,代表這個地圖上有幾條路。

  接下來R行,每行包含兩個相異正整數X.Y,代表編號為X.Y的城市間有路相通。

  再接下來有一個正整數P,代表對於這張地圖,房布要問你多少問題。

  接下來P行,每行有一個正整數為K,當K=1時,後面會有一個正整數A,代表房布想問你編號A的城市跟多少個城市有路可以直接連通;當K=2時,後面會有兩個相異正整數A.B,代表房布想問你編號A.B的城市間是否有路可以直接連通。

 

對於20%的測試資料,保證K=1

對於另外20%的測試資料,保證K=2

對於上列40%的測試資料,2<=N<=10,1<=R<=10

對於100%的測試資料,2<=N<=100,1<=R<=10000,1<=A.B<=N,1<=P<=10000,且保證每一組(X,Y)皆不重複

Output

  對於每筆房布的詢問,請輸出一行答案,如果是K=1的問題,請輸出一個整數代表有多少個城市和編號A的城市有路直接連通;如果是K=2的問題,如果編號為A.B的兩城市間有路可以直接連通,請輸出「Yes」(不含引號),反之請輸出「No」(不含引號)。

Sample Input #1
4
3
1 2
1 3
2 4
4
1 1
2 3 1
2 4 1
1 3
Sample Output #1
2
Yes
No
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 5.0s , <1M
公開 測資點#1 (20%): 5.0s , <1M
公開 測資點#2 (20%): 5.0s , <1M
公開 測資點#3 (20%): 5.0s , <1M
公開 測資點#4 (20%): 5.0s , <1M
Hint :
Tags:
出處:
2013延平暑假快樂程設營練習賽題目 [管理者: Nineguan (VAC+03_小馬) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」