分数: 7 点
问题陈述
我们有 N 药品种类编号 1 to N.
药物的效率由以下整数表示 1 to 100;越大,效率越高。药物功效 i is A_i。 (全部 A_i 是不同的。)
这些药物还含有过敏原(引起过敏反应的物质)。过敏原由整数表示 1 to 2 \times 10^5和药物 i 包含 C_i 过敏原 X_{i,1}, X_{i,2}, \dots, X_{i,C_i}.
你被给予 Q 查询,应按照指令处理。的 p第一个查询如下:
人 p 对以下物质过敏 D_p 过敏原 Y_{p,1}, Y_{p,2}, \dots, Y_{p,D_p},并且不得给予含有一种或多种这些过敏原的药物。
考虑给予人员 p 药物之一 1 毒品 N。打印出代表可以给予该人的最有效药物的数字 p。如果不能给予药物,请打印 -1.
约束
- 1 \leq N \leq 100
- 1 \leq A_i \leq 100
- A_i \neq A_j if i \neq j.
- 0 \leq C_i
- 0 \leq \sum_{i=1}^N C_i \leq 10^5
- 1 \leq X_{i,j} \leq 2 \times 10^5
- X_{i, j} \neq X_{i, k} if j \neq k.
- 1 \leq Q \leq 10^5
- 0 \leq D_p
- 0 \leq \sum_{p=1}^Q D_{p} \leq 10^5
- 1 \leq Y_{p,q} \leq 2 \times 10^5
- Y_{p,q} \neq Y_{p,r} if q \neq r.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_N
C_1
X_{1,1} X_{1,2} \dots X_{1,C_1}
C_2
X_{2,1} X_{2,2} \dots X_{2,C_2}
\vdots
C_N
X_{N,1} X_{N,2} \dots X_{N,C_N}
Q
D_1
Y_{1,1} Y_{1,2} \dots Y_{1,D_1}
D_2
Y_{2,1} Y_{2,2} \dots Y_{2,D_2}
\vdots
D_Q
Y_{Q,1} Y_{Q,2} \dots Y_{Q,D_Q}
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
3 10 9 8 3 1 2 3 1 1 2 2 3 4 0 1 1 1 2 2 1 2
示例输出 1
1 3 2 -1
这里是有关药物和查询的信息摘要。
- 药物 1 的效率为 10 并含有过敏原 1, 2,和 3.
- 药物 2 的效率为 9 并含有过敏原 1.
- 药物 3 的效率为 8 并含有过敏原 2 和 3.
- 人 1 可以给予任何药物。
- 人 2 不得服用含有过敏原的药物 1.
- 人 3 不得服用含有过敏原的药物 2.
- 人 4 不得服用含有一种或多种过敏原的药物 1 和 2.