题目描述

塔尖乐园是一个神奇的游乐园，由 $n$ 个“魔法塔”组成，每个塔之间有若干单向传送门。每个传送门只能从一个塔传送到另一个塔。

你作为乐园的管理员，需要处理一些问题：对于每个查询塔 $x$，你需要统计：

1. 编号最小的塔可以到达塔 $x$ 是哪个塔。
2. 从塔 $x$ 出发能够到达编号最大的塔是哪个塔。

塔编号为 $1$ 到 $n$。

输入格式

第一行包含两个整数 $n, m$ $(1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5)$，分别表示塔的数量和传送门的数量。

接下来 $m$ 行，每行包含两个整数 $u, v$ $(1 \le u, v \le n)$，表示有一条从塔 $u$ 指向塔 $v$ 的单向传送门。

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

接下来 $q$ 行，每行一个整数 $x$ $(1 \le x \le n)$，表示查询的塔编号。

输出格式

对于每个查询塔 $x$，输出一行两个整数表示查询答案。

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

1 5
1 5
3 5

1 0
1
1

1 1