回分類題庫
h101: A.神祕的地圖
關鍵字: NPSC 2012 高中組初賽

測資點 : 2 | Time Limit : 20000 ms | Memory Limit : 128000 KB
Accepted : 16 Times / 16 Users | Submit : 30 Times / 18 Users | Accepted rate : 89%
題目加入時間 : 2013-11-04 15:34

Content: 简体中文

相傳,有個古老而神秘的帝國,曾經有過非常繁榮的時代,但是經過幾次戰爭以及災禍之後,帝國便在歷史中消失了。但也有另外一派的人相信現在的都市其實是從帝國逐漸演變而成,只是有幾個城市以及連接那些城市的道路消失了。

一天,小小郭在家中的深處找到了一張神秘的地圖,有點像是他所居住的地方,但是在地圖上卻多了好幾個城市,因此他懷疑這就是傳說中古老帝國的地圖。

為了驗證這個說法,小小郭想到了一個辦法:如果帝國是都市的前身,那麼每個現在的新城市一定都是古老帝國中的某個舊城市(彼此有對應關係)。若這些舊城市之間的道路連接狀況與新城市的道路連接狀況相同的話,則我們就說帝國與都市有完整對應,代表帝國真的是都市的前身。要注意的是,若兩個城市之間有 k 條道路的話,對應之後也必須要有 k 條道路,才可以說有對應關係!(k>=0)

但是小小郭覺得這個工作太麻煩了,你能幫幫他嗎? 

Input:

測試資料第一行有一個正整數T(T<=20)表示接下來總共有幾筆測試資料。

每一筆測試資料的第一行有兩個整數 N1,M1 以一個空白隔開,N1 代表地圖上城市的數量,並由 0 編號到 N1−1、M1 代表道路的個數。城市接下來有 M1 行,每行有兩個整數 ai, bi,代表該條道路連接城市 ai 及城市 bi。(0<=ai,bi<N1)接下來的一行有兩個整數 N2,M2 分別以空白隔開,代表有現在的城市的數量,並由 0 編號到 N2−1,以及道路的個數。接下來有 M2 行,每行有兩個整數 pi, qi,代表該條道路連接城市 pi 及城市 qi 。(0<=pi,qi<N2)

 

我們保證 N2<=N1<=10 以及 M1,M2<=50。 

Output:

對每筆測試資料輸出一行,如果可以成功的對應,輸出“YES”(不含引號),若無法對應,則輸出“NO”(不含引號)。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4 4
0 1
1 2
2 3
0 3
3 2
0 1
1 2
4 4
0 1
1 2
2 3
0 3
3 3
0 1
1 2
0 2

Sample Output :

YES
NO

Hint :

範例說明: 

第一筆測試資料中,將 0 對應到 0,1 對應到 1,2 對應到 2,即可成功對應。

第二筆測試資料中,無法找到任何對應。 

Author :

NPSC 2012 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum