#2516. 游船之旅

游船之旅

Description

河流总是形成一棵树(以村庄为节 点),超过两条河流时可以在交叉路口汇入。游船的定价政策非常简 单:两个村庄之间的每条河流都有一个价格(两个方向的价格相同), 任意两个村庄之间的旅行价格都是唯一的。已知河流网络的描述,包括 河段的价格和整数序列x1,,xkx_1 , …, x_k 。对于每个xix_i ,都应该确定河网中 是否存在一对村庄(a,b)(a , b ),使得aabb 之间的旅行价格恰好是xix_i

Format

Input

输入包含多个测试用例,每个测试用例的第1行都包含单个 整数N1N104N (1≤N ≤10^4 ),表示村庄数。接下来的NN 行,第ii 行描述村 庄ii ,包含以空格分隔的整数d1,c1,dj,cj,dki,cki0d_1 ,c_1, …d_j, c_j, …d_{k_i} ,c_{k_i} 0djd_j 表示从村庄ii 出发的河流直接流向的村庄编号,cjc_j 表示村庄iidjd_j 之间的旅行价格,2djN0cj10002≤dj ≤N ,0≤cj ≤1000。村庄11在河流的源头,因为村庄 11 始终对应于最大河流的入海口,因此任何 did_i 不可能等于 1

接下来的MM100M (M≤100)行查询,第ii 个查询包含单个整数xi1xi107x_i (1≤x_i ≤10^7 )。每个 测试用例都由包含数字00的单行结束,整个输入由包含数字00的单行结 束。

Output

对每个测试用例,都输出M 行查询的答案。若在河网中存 在两个价格为xix_i 的村庄,则输出“AYE”,否则输出“NAY”。在每个 测试用例后面都单行输出“.”。

Samples

6
2 5 3 7 4 1 0
0
5 2 6 3 0
0
0
0
1
8
13
14
0
0
AYE
AYE
NAY
AYE
.

来源

POJ2114