题目描述

图 $\text G$ 是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点 $v,u$ 的最短路径就是从 $v$ 到 $u$ 经过边最少的路径。所有包含在 $v-u$ 的最短路径上的顶点被称为 $v-u$ 的 Geodetic 顶点，这些顶点的集合记作 $I(v,u)$。

我们称集合 $I(v,u)$ 为一个 Geodetic 集合。

例如下图中，$I(2,5)=\{2,3,4,5\}$，$I(1,5)=\{1,3,5\}$，$I(2,4)=\{2,4\}$。

给定一个图 $\text G$ 和若干点对 $v,u$，请你分别求出 $I(v,u)$。

输入格式

第一行为两个整数 $n,m$，分别表示图 $\text G$ 的顶点数和边数（顶点编号为 $1\sim n$）。
接下来 $m$ 行，每行两个整数 $a,b$，表示 顶点 $a$ 和 $b$ 之间有一条无向边。
第 $m+2$ 行有一个整数 $k$，表示给定的点对数。
接下来 $k$ 行，每行两个整数 $v,u$，表示每个点对的起点和终点。

输出格式

共 $k$ 行，对于输入文件中每一个点对 $v,u$，按顶点顺序一行输出 $I(v,u)$ 里面的所有点的编号。

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

2 3 4 5
1 3 5
2 4

提示

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