题目描述

强哥的机器人朋友们建立了一个友谊网络！

这个网络有 $n$ 个机器人（编号为 $1\sim n$），他们之间有 $m$ 对直接朋友关系。每个机器人最多只能和其他机器人建立一条直接朋友关系，并且机器人不可能和自己成为朋友。

强哥发现，在友谊网络中，机器人 $v$ 和机器人 $u$ 之间的最短朋友链长度就是从 $v$ 到 $u$ 需要经过的最少朋友数量。所有包含在 $v$ 到 $u$ 的最短朋友链中的机器人，都被称为 $v$-$u$ 的“友谊核心”机器人，这些机器人的集合记作 $I(v,u)$。

例如下图中，$I(2,5)=\{2,3,4,5\}$（机器人2通过3、4连接到5），$I(1,5)=\{1,3,5\}$，$I(2,4)=\{2,4\}$。

现在强哥想知道，对于给定的若干对机器人朋友，他们之间的友谊核心机器人有哪些？

输入格式

第一行为两个整数 $n,m$，分别表示机器人数量和朋友关系数量。

接下来 $m$ 行，每行两个整数 $a,b$，表示机器人 $a$ 和机器人 $b$ 是直接朋友。

第 $m+2$ 行有一个整数 $k$，表示强哥想知道的朋友对数量。

接下来 $k$ 行，每行两个整数 $v,u$，表示每对朋友链的起点和终点。

输出格式

共 $k$ 行，对于每一对机器人 $v,u$，按照编号顺序一行输出 $I(v,u)$ 中的所有机器人编号。

样例输入1

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

样例输出1

2 3 4 5
1 3 5
2 4

数据范围

对于所有数据，满足 $1\leqslant n\leqslant 40$，$1\leqslant m\leqslant \frac{n(n-1)}2$。