4377. [郑轻校赛 2026] 保卫萝卜

Problem B. 保卫萝卜

在一片田野上，有 $n$ 个庄园，按海拔从高到低编号为 $1,2,\dots,n$（编号越小海拔越高）。庄园间建有若干水道，水只能从高海拔流向低海拔，且保证从 $1$ 号庄园（最高点）出发，水可到达所有其他庄园。

$1$ 号庄园种有一个珍贵萝卜。外星人在某些庄园投放兔子，兔子只会逆流而上，目标是到达 $1$ 号庄园吃掉萝卜。小赵可以在一个庄园设置拦截点，兔子一旦经过该点即被抓住。兔子可能选择多条逆流路径，小赵希望无论兔子走哪条路径，都会被拦截。换言之，拦截点必须位于每一只兔子所有可能的逆流路径上。

外星人会多次投放兔子。对于每次投放，请找出一个能拦截所有兔子的庄园。若有多个满足条件的庄园，输出其中编号最大的一个。

Input

第一行包含两个整数 $n,m$ $(1 \le n \le 2\times 10^5,\ n-1 \le m \le 2\times 10^5)$，分别表示庄园数和水道数。

接下来 $m$ 行，每行包含两个整数 $u,v$ $(1 \le u < v \le n)$，表示一条从 $u$ 流向 $v$ 的水道。保证无自环、无重边，且从 $1$ 出发可到达所有节点。

接下来一行包含一个整数 $q$ $(1 \le q \le 2\times 10^5)$，表示询问次数。

接下来 $q$ 行，每行描述一次投放：第一个整数 $k$ $(1 \le k \le n)$，随后 $k$ 个互不相同的整数 $x_1, x_2, \dots, x_k$ $(1 \le x_i \le n)$，表示投放兔子的庄园编号。保证所有询问中 $k$ 的总和不超过 $2\times 10^5$。

Output

对于每个询问，输出一个整数，即符合条件的庄园编号。

Example

样例输入1

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

样例输出1

1
5
2

Note

水道构成：$1 \rightarrow 2,\ 1 \rightarrow 3,\ 2 \rightarrow 4,\ 3 \rightarrow 4,\ 2 \rightarrow 5$。

第一个询问：兔子在 $\{4,5\}$，只有在 $1$ 号庄园设防才能拦截所有兔子。

第二个询问：兔子在 $\{5\}$，在 $\{1,2,5\}$ 中任一处设防均可，选择编号最大的 $5$。

第三个询问：兔子在 $\{2,5\}$，在 $\{1,2\}$ 中任一处设防均可，选择编号最大的 $2$。

来源