Geodetic集合
题目描述
图 $\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\}$。
![](https://cdn.luogu.com.cn/upload/image_hosting/26c7a19d.png)
给定一个图 $\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)$ 里面的所有点的编号。
输入输出样例
输入样例 #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$。