回分類題庫
h086: A.旅行地圖
關鍵字: NPSC 2011 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 20 Times / 19 Users | Submit : 41 Times / 23 Users | Accepted rate : 83%
題目加入時間 : 2012-11-04 02:26

Content: 简体中文

規規和散散是感情十分要好的兄弟,他們兩個人都很熱愛旅行,所以常常一起出去旅遊。

最近他們的叔叔在整理規規和散散之前一起出去玩時寫下的筆記,發現規規在記錄事情之前總會先清楚地標明時間和地點;散散每次出門旅遊都會更換一本新的記事本,也不會順手記下日期,加上散散喜歡用「感覺」記錄一切,總是使用「天空很大的地方」或「海水很藍的沙灘」這一類的詞來代替地名,所以叔叔搞不清楚規規和散散的日記要如何對應起來。

在叔叔觀察了很久之後,發現規規和散散兩個人都有記錄大眾運輸工具路線圖的習慣,規規會根據地點之間的遠近和相對位置作圖,並且記錄地點之間是否有大眾運輸工具可直達;散散畫的地圖只在乎地點之間能否直達,加上散散獨家的「地名記錄法」,使得叔叔還是沒辦法迅速地把兩兄弟畫的地圖對應起來。(如果我們可以對兩張地圖上的地點找到一組一對一的配對,讓兩張地圖上的地點之間的直達關係都相同,我們就當作這兩張地圖能夠對應;對於下圖而言,節點上的數字即代表其中一組配對。)

聰明的你,能不能夠幫助叔叔把規規和散散畫的地圖對應起來呢?

Input:

輸入的第一行有一個正整數 T,代表測試資料的組數(1<=T<=100)。

每組測試資料的第一列有兩個整數 N 和 M,代表地圖內有 N 個地點(1<=N<=8)和 M 個關係,關係不會重複也沒有方向性。

接下來的 M 行描述規規畫的地圖,地名皆由一個大寫字母所代表,每一行包含兩個地名,表示這兩個地點之間可以直達;再下來的 M 行描述散散畫的地圖,地名皆由一個小寫字母所代表。

Output:

對於每組測試資料輸出兩個地圖能否對應,能就輸出 yes,否則輸出 no。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
8 12
A B
A D
A E
B C
B F
C D
C G
D H
E F
E H
F G
G H
a g
a h
a i
b g
b h
b j
c g
c i
c j
d h
d i
d j
4 3
A B
B C
C D
a b
a c
a d
3 1
A E
c d

Sample Output :

yes
no
yes

Hint :

Author :

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

  Solve it!   Status Forum