2013年8月13日 星期二

1198 - The Geodetic Set Problem

G = (V, E) 表示一連通圖,不存在 loops(自己連自己) 和重覆的邊,V, E 分別表示節點與邊。

對於 u, v V 必然會存在一條最短路徑,而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合,而 S V


如果 I(D) = V,則這節點集合 D 被稱作為 G 的其中一個 geodetic set The geodetic set problem 就是要檢驗 D 是否為 geodetic set

以上圖為例,I(2, 5) = {2, 3, 4, 5},即所有可能在最短路徑上的所有點,然而
I(2, 5) 並不是一個 geodetic set,因為並不等於 {1, 2, 3, 4, 5}。

假如 D = {1, 2, 5},則 I(D) = V,同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set,但
{3, 4, 5} 卻不是,因為節點 1 並不在 I(D) 中。


Input

輸入有多組測資,每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。


接下來會有 n 行,在第 i(1 <= i <= n)上會有數個整數,表示與節點編號 i 相連的點。

接著會有一行一個整數 q,表示接下有多少組詢問
 

每組詢問一行,行上的每個整數 D 集合內的節點編號。
Output

對於每組詢問的 D,判斷 D 是否為
geodetic set

Sample Input

5
2 3
1 3 4
1 2 5
2 5
3 4
6
1 2 3 4 5
1 2 5
2 4
1 3 4
1 4 5
3 4 5

 
Sample Output

yes
yes
no
yes
yes
no

沒有留言:

張貼留言