题目描述

在一所非常著名的大学里，经常会有重要人物前来讲有趣的课程。一场讲座通常由一系列演绎推理组成，形式为“由 $A$ 可推出 $B$”。几乎所有人都有逻辑思维能力：如果他们知道 $A$ 推出 $B$，且 $B$ 推出 $C$，那么他们就可以认为 $A$ 推出 $C$。因为讲师不喜欢完全无意义的推理，所以他从不会两次推出同一个结论；也就是说，不存在两条形如“由 $A$ 推出 $B$”和“由 $C$ 推出 $B$”的推理。

若干学生来听这场讲座。每个学生已经对世界有一些认识：他认为某些命题为假，某些命题为真。讲座过程中，讲师依次告诉他们一些演绎推理；然而在某个时刻，这些推理可能与某个学生已有的认识发生矛盾。例如，学生认为 $A$ 为假、$B$ 为真，而讲师说“由 $B$ 推出 $A$”。

请你对每个学生求出：讲师的第几个推理第一次导致它与该学生的世界观发生矛盾。所谓矛盾，是指学生从自己认为为真的命题集合出发，借助讲师已经给出的演绎推理，可以逻辑推出一个他认为为假的命题。

举一个典型讲座的例子。假设讲师依次给出推理：“由 $A$ 推出 $B$”，“由 $C$ 推出 $D$”，“由 $B$ 推出 $C$”。某个学生认为 $A$ 为真、$D$ 为假。听到第一条推理后，学生会认为 $B$ 为真；听到第二条推理后仍未发生矛盾；听到第三条“由 $B$ 推出 $C$”后，学生会认为 $C$ 为真，并且借助第二条推理推出 $D$ 为真，这与他原先认为 $D$ 为假矛盾。

如果另一个学生认为 $A$ 为假、$D$ 为真，则对他而言不会在任何时刻发生矛盾：即使知道了讲师的全部推理，他也不能从自己认为为真的命题推出假的命题。

输入格式

第一行输入整数 $M$，表示讲师给出的演绎推理数量（$1 \le M \le 500\,000$）。

接下来 $M$ 行，每行描述一条推理，包含两个整数 $a_i,b_i$，分别表示该推理的前件和后件（$a_i \ne b_i$，$1 \le a_i,b_i \le 500\,000$）。也就是说，讲师声明“由命题 $a_i$ 可推出命题 $b_i$”。保证所有 $b_i$ 互不相同。

下一行输入整数 $Q$，表示学生数量（$1 \le Q \le 500\,000$）。接下来给出每个学生的知识描述。

每个学生的描述以整数 $t_i$ 开始，表示他认为为真的命题数量；随后给出 $t_i$ 个命题编号。接着给出整数 $f_i$，表示他认为为假的命题数量；随后给出 $f_i$ 个命题编号。

所有命题编号都在 $1$ 到 $500\,000$ 之间。每个学生至少知道一些内容，即 $t_i+f_i>0$。同一个学生描述中出现的所有命题编号互不相同。所有学生描述中提到的命题总数，即所有 $t_i+f_i$ 之和，不超过 $500\,000$。

输出格式

对每个学生输出一个整数：使其世界观第一次产生矛盾的推理编号；如果他与讲师给出的全部推理都不矛盾，输出 $-1$。

样例

样例 1

输入：

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

输出：

3
4
-1

样例 2

输入：

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

输出：

3
5
2
5
4
5

评分方式

测试点分为四组：

每组测试只有在通过该组全部测试后才得分。每一组只会在通过所有前置组测试后进行评测。